学步园

/*
 * heap_demo.c
 * mike-w
 * 2012-7-23
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

#define HEAP_SIZE (2<<13)
#define BUF_SIZE 256

int swap(int *e1, int *e2)
{
	int tmp=*e1;
	*e1=*e2;
	*e2=tmp;
	return 0;
}

int heap_in(int *heap, int e)
{
	if(heap[0]==HEAP_SIZE)
	{
		puts("heap is full :-(");
		return -1;
	}
	heap[++heap[0]]=e;
	int c=heap[0], p=c/2;
	while(p>0 && heap[p]>heap[c])
		swap(heap+p, heap+c), c=p,p=c/2;
	return 0;
}

int heap_out(int *heap, int *e)
{
	if(!heap[0])
	{
		puts("heap is empty :-(");
		return -1;
	}
	*e=heap[1];
	swap(heap+1,heap+heap[0]);
	heap[0]--;
	int p=1, lc, rc, x;
	while(1)
	{
		x=p;
		lc=2*p;
		rc=2*p+1;
		if(lc<=heap[0] && heap[lc]<heap[x])
			x=lc;
		if(rc<=heap[0] && heap[rc]<heap[x])
			x=rc;
		if(x!=p)
			swap(heap+x, heap+p), p=x;
		else
			break;
	}
	return 0;
}

int get_top(int *heap,int *e)
{
	if(!heap[0])
	{
		puts("heap is empty :-(");
		return -1;
	}
	else
	{
		*e=heap[1];
		return 0;
	}
}

void good_bye(void)
{
	puts("good bye :-)");
	return;
}

int help(void)
{
	puts("instructions:");
	puts("insert [number]: insert number into the heap");
	puts("pop: \t\tpop out a number from the heap");
	puts("get_top: \tdisplay the number at the top of the heap");
	puts("help: \t\tdisplay this message");
	puts("quit: \t\tquit");
	return 0;
}

int get_command(int *p)
{
	char buf[BUF_SIZE];
	printf("=>");
	scanf("%s",buf);
	if(!strcmp(buf,"insert"))
	{
		scanf("%d",p);
		return 1;
	}
	else if(!strcmp(buf,"pop"))
		return 2;
	else if(!strcmp(buf,"get_top"))
		return 3;
	else if(!strcmp(buf,"help"))
		return 4;
	else if(!strcmp(buf,"quit"))
		return 5;
	else
		return -1;
}

int main(void)
{
	int p1,cmd;

	atexit(good_bye);
	
	int heap[HEAP_SIZE],e;
	memset(heap,0,sizeof(heap));

	/* welcome msg */
	puts("*****************************");
	puts("*      heap demo v1.0       *");
	puts("*      author: mike-w       *");
	puts("*         2012-7-23         *");
	puts("*****************************");
	help();
	
	while((cmd=get_command(&p1)))
	{
		switch(cmd)
		{
			case 1: /* insert */
				if(!heap_in(heap, p1))
					printf("%d is inserted into the heap\n", p1);
				break;
			case 2: /* pop */
				if(!heap_out(heap,&e))
					printf("%d is popped out from the heap\n",e);
				break;
			case 3: /* get_top */
				if(!get_top(heap, &e))
					printf("%d is at the top of the heap\n",e);
				break;
			case 4: /* help */
				help();
				break;
			case 5: /* quit */
				exit(0);
				break;
			default:
				puts("invalid command ==!");
		}
	}
	return 0;
}