우선 대기 열 및 기본 작업 의 더미 구현

/*
	         ：               
	                 S     ，   
	             ，     。
	              ：
		insert(S,x) S     x;
		maximum(S)  S        ;
		extract-max(S)      S        ;
		increase-key(S,x,k)   x       k，  k    x     

	              ：
		insert(S,x) S     x;
		minimum(S)  S        ;
		extract-min(S)      S        ;
		decrease-key(S,x,k)   x       k，  k    x     

	                    
	                    
	           
	           
*/

#include<stdio.h>
#include<stdlib.h>
#define N 6

static int heapSize=N;
/*
               
*/
//     
int parent(int index)
{
    return (index-1)/2;
}
 
//     
int left(int index)
{
    return (index<<1)+1;
}
 
//     
int right(int index)
{
    return (index+1)<<1;
}

/*
          ，              
          logn
*/
int maxHeapify(int *A,int index,int size)
{
    int L=left(index);
    int R=right(index);
    int tmp;
    int largestIndex;
    if(L<size && *(A+index)<*(A+L)) {
        largestIndex=L;
    } else {
	largestIndex=index;
    }
    if(R<size && *(A+largestIndex)<*(A+R)) {
        largestIndex=R;
    }
    if(index!=largestIndex) {
        tmp=*(A+index);
        *(A+index)=*(A+largestIndex);
        *(A+largestIndex)=tmp;
        maxHeapify(A,largestIndex,size);
    }
    return 0;
}

/*
                      ，  
                 
          nlogn
*/
int buildMaxHeap(int *A)
{
    int size=N;
    //               
    int need=heapSize/2-1;
    int i;
    for(i=need;i>=0;i--) {
        maxHeapify(A,i,heapSize);
    }
    return 0;
}

/*
         
               ，        
                     
*/
int heapSort(int *A)
{
    buildMaxHeap(A);
    int j;
    int size=heapSize;
    int i;
    int tmp;
    for(i=N-1;i>=1;i--) {
        tmp=*A;
        *A=*(A+i);
        *(A+i)=tmp;
        size--;
        maxHeapify(A,0,size);
    }
    return 0;
}

//------------------          -----------------------//

/*
	       
*/
int heapMaxElement(int *A)
{
	return A[0];
}

/*
	              
*/
int heapExtractMax(int *A)
{
	if(N<1) {
		printf("Heap error!");
	}
	int max=heapMaxElement(A);
	A[0]=A[heapSize-1];
	heapSize=heapSize-1;
	maxHeapify(A,0,heapSize);
	return max;
}

/*
	   i     ，       
*/
int heapIncreaseKey(int *A,int index,int newValue) 
{
	if(newValue<*(A+index)) {
		printf("            ！");
		return 1;
	}
	*(A+index)=newValue;
	while(index>0&&*(A+index)>*(A+parent(index))) {
		int temp;
		temp=*(A+index);
		*(A+index)=*(A+parent(index));
		*(A+parent(index))=temp;
		index=parent(index);
	}
	return 0;
}

/*
	         
*/
int heapInsert(int *A,int key)
{
	heapSize=heapSize+1;
	int *b=malloc(sizeof(int)*heapSize);
	b=A;
	*(b+heapSize-1)=key-1;
	heapIncreaseKey(b,heapSize-1,key);
	A=b;
	return 0;
}

int main()
{
	int b[N]={2,1,3,2,5,4};
	int* a=b;
	//  ：     
	buildMaxHeap(a);
	printf("          6
");
	heapIncreaseKey(a,0,6);
	printf("%d
",*a); 

	printf("     7
");
	heapInsert(a,7);
	printf("%d
",*a); 

	printf("      
");
	printf("%d
",*a);

	printf("      
");
	printf("%d
",heapExtractMax(a));

	printf("      
");
	printf("%d
",*a);
	
	return 0;
}

zzw@zzw-ThinkPad-Edge-E430c:~/Algorithms/chap6/demo1$ ./priorityQueue 
          6
6
     7
7
      
7
      
7
      
6