langc_algo_heap_heapsort_pqueue.c

#include <stdio.h>
//refer to https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
 
#define heap_parent(n) ((n-1)/2) 
#define heap_left(n)   ((2*n)+1) 
#define heap_right(n)  ((2*n)+2) 

typedef enum{
	SET_HEAPNULL=0,
	SET_UPHEAP,		
	SET_DOWNHEAP,	
}HEAP_DIRECTION;

#define TOP_HEAVY_HEAP

void printarry(int arry[],int lens) //debug
{
	int i;
	
	printf("----( arry lens=%d )\n",lens);
	for(i=0;i<lens;i++)
		printf("[%02d] ",arry[i]);
	printf("\n");
	
}

void swap(int a[], int b[])
{
	int tmp;
	static int cnt=1;	
//	printf("%d swap %d %d \n",cnt++,*a,*b);	//debug
	tmp = *a;
	*a = *b;
	*b = tmp;
}

int makeheap(int * arr, int pos, int heap_size, int updown)  
{
	int left, right, parent;
	
	if(updown == SET_HEAPNULL)
		return -1;
	
	while(pos < heap_size) // this loop is only for extracting top-node and direction: SET_DOWNHEAP
	{
		left   = heap_left(pos);
		right  = heap_right(pos);
		parent = pos; /*  1. compare an parent with two children (left,right)
		                  2. get the largest value
		                  3. heap_size means heap's length */

#if defined(TOP_HEAVY_HEAP)		
		if(( left < heap_size) && (arr[left]>arr[parent])) 
			parent = left;
		if((right < heap_size) && (arr[right]>arr[parent])) 
			parent = right;
#else
		if(( left < heap_size) && (arr[left] <  arr[parent])) 
			parent = left;
		if((right < heap_size) && (arr[right] < arr[parent])) 
			parent = right;
#endif

		if(parent == pos) break;  // now is the largest value,  
		
		swap(&arr[pos], &arr[parent]); // pos is the largest value after swap
			
		if(updown == SET_UPHEAP) break; //if used makeupheap, not working loop
		pos = parent;  			// for down heap

	}
	
	if(updown == SET_DOWNHEAP){
		printarry(arr,heap_size); // debug 
	}
	
}
 

void makeupheap(int *arr, int length) // for inserting new nodes , direction: SET_UPHEAP , up 
{
	int parent=length-1; //last node 
   	
	for(parent=heap_parent(parent); parent >=0; parent--) //check from a parents of last node to top node
		makeheap(arr, parent, length,SET_UPHEAP); 

 	printf("after new built up-Heap lens=%d (up) \n",length); // debug  		
	printarry(arr,length);                                 	  // debug 
   
}

// -------------Heap Sort ------------------------

void heapsort(int * arr, int length)
{
	int last_node;
	
	makeupheap(arr, length); // made top-heavy heap ,top node is the largetst value  arr[0] 	

 	printf("before heapsort lens=%d \n",length); // debug
    
	for(last_node = length-1; last_node > 0; last_node--)
	{	
		/* 1.  swap the largest value [0] and last node, extract top-node  
		   2.  make new heap except last node  (direction : down)
		       last_node means length and last_node 
		   3.  repeat 1,2                                           */
		
		swap(&arr[0], &arr[last_node]);
		makeheap(arr, 0, last_node,SET_DOWNHEAP); // make heap , direction : down 
	}
	
 	printf("after heapsort lens=%d \n",length); // debug 	
	printarry(arr,length);                      // debug 
}

// ------------------  Priority Queue --------------

#define PQUEUE_MAX 100 
int pqueue_size=0;

int pqueue_init(int arr[], int lens)
{
	if( lens >= PQUEUE_MAX )
		return -1;
		
	makeupheap(arr,lens); //make heap , direction : up
	pqueue_size=lens;
	
	printf("pqueue_init: lens=%d \n",pqueue_size); // debug,
	
	return 0;
}

int pqueue_insert(int arr[], int* data)
{

	if(pqueue_size >= PQUEUE_MAX )  
		return -1;
	
	printf("pqueue_insert: lens=%d data=%d \n",pqueue_size,*data); // debug,
	
	arr[pqueue_size++]=*data;	// last node 
	makeupheap(arr,pqueue_size);   // make heap , direction : up  
	
	return 0;
}

int pqueue_extract(int arr[], int* data) // have problem, can't use top nodes arrarys 
{

	int last_node;
	
	last_node = pqueue_size - 1; 

	swap(&arr[0], &arr[last_node]);
	makeheap(arr, 0, last_node,SET_DOWNHEAP); //make heap , direction : down 		
	*data =  arr[last_node];		
	
	pqueue_size=last_node;

	printf("pqueue_extract: lens=%d data=%d\n",pqueue_size,*data); // debug,
  
	return 0;		
}

int main(void)
{
	int arr1[]   ={25,20,22,17,19,10,12,15,7,9,18,24};
	int arr2[PQUEUE_MAX]={25,20,22,17,19,10,12,15,7,9,18,24};	
	int lens1;
	int lens2;
	int data,i;

	// input
	lens1=sizeof(arr1)/sizeof(int);
	lens2=sizeof(arr1)/sizeof(int);

 	printf("origin array lens=%d \n",lens1); // debug
	printarry(arr1,lens1);

//heapsort test 	
	heapsort(arr1, lens1);

//priority queue test start 	
	pqueue_init(arr2,lens1); // now, same size is lens1 with lens2 
	
	for(i=0;i< 10; i++) // everytime check queue insert and extract 
	{
		data= i* 5+3 ; // test value, 
		pqueue_insert(arr2,&data);     
		pqueue_extract(arr2,&data);	
	}

	for(i=0;i< 15; i++) 
	{	
		data= i* 5 + 3+1 ; // test value, 
		pqueue_insert(arr2,&data);     
	}
	
	for(i=0;i< 10; i++) 
		pqueue_extract(arr2,&data);	
			
	return 0;
}