#include <stdio.h>
typedef struct dasim {
	int key;
	int link;
} element;
/*-------------------------------------------------------------- main ---*/
main()
{
	int i,n;
	static char buf[80];
	element list[11];
	int array[11]={0,61,5,77,1,26,11,59,15,48,19};

	n=10;
	while(buf[0] != 'q') {
		for(i=0;i<=n;i++)
			list[i].key = array[i];
		gets(buf);
		switch (buf[0]) {
		case 's':
			selection(list,n);
			break;
		case 'h':
			heapsort(list,n);
			break;
		case 'b':
			binary(list,n);
			break;
		}
	}
	printout(list);
}
	struct dasima {
		int item;
		struct dasima *lptr;
		struct dasima *rptr;
	} *head, *curr, *prev;
binary(element list[], int n)
{
	int i,j;

	prev = head = (struct dasima *)malloc(sizeof(struct dasima));
	head -> item = list[1].key;
	head -> lptr = head -> rptr = NULL;

	for(i=2; i<=10;i++) {
		prev = head;
		/* printtree(head); */
		curr = (struct dasima *)malloc(sizeof(struct dasima));
		curr -> item = list[i].key;
		curr -> lptr = curr -> rptr = NULL;
		while (prev) {
		if(curr -> item > prev -> item) {
			if(prev -> rptr) prev = prev -> rptr;
			else {
				prev -> rptr = curr;
				break;
			}
		}
		else {
			if(prev -> lptr ) prev = prev -> lptr;
			else {
				prev -> lptr = curr;
				break;
			}
		}
		}
	}
	printtree(head);
}
printtree(struct dasima *head)
{
	if(head -> lptr) printtree(head -> lptr);
	printf("%d\t",head -> item);
	if(head -> rptr) printtree(head -> rptr);
}

/*----------------------------------------------------------- heapsort ---*/
selection(element list[], int n)
{
	int i,j,k;
	element temp;
	i=n;
	while(i>0) {
		j=i;
		for(k=0;k<i;k++) {
			if(list[k].key>list[j].key) j=k;
		}
		temp.key=list[i].key;
		list[i].key=list[j].key;
		list[j].key=temp.key;
		i--;
	}
	printout(list);
}
heapsort(element list[], int n)
{
	int i;
	element temp;

	for(i=n/2; i>0; i--)
		adjust(list,i,n);
	for(i=n-1; i>0; i--)
	{
		/* SWAP FIRST ELEMENT WITH ELEMENT I+1 */
		temp.key=list[1].key;
		list[1].key=list[i+1].key;
		list[i+1].key=temp.key;
		adjust(list,1,i);
	}
	printout(list);
}
/*------------------------------------------------------- printout -------*/
printout(element list[])
{
	int i;
	for(i=0;i<=10;i++) printf("%d\n",list[i].key);
}
/*-------------------------------------------------------------- adjust --*/
adjust(element list[], int root, int n)
{
	int child, rootkey;

	rootkey=list[root].key;
	child=2*root;
	while(child<=n) {
		if((child<n)&&(list[child].key < list[child+1].key)) child++;
		if(rootkey>list[child].key) break;
		else {
			list[child/2].key=list[child].key;
			child*=2;
		}
	}
	list[child/2].key=rootkey;
}