优先队列

#include<stdio.h>#include<limits.h>#define SIZE 100#define LEFT(i) i<<1#define RIGHT(i) (i<<1)+(1)#define PARENT(i) i>>1void swap(int *p,int *q){ int tmp=*p; *p=*q; *q=tmp;}void maxHeapIFY(int *arr,int i,int heapsize){ int l=LEFT(i); int r=RIGHT(i); int largest; if(l<=heapsize&&arr[l]>arr[i]) largest=l; else largest=i; if(r<=heapsize&&arr[r]>arr[largest]) largest=r; if(largest!=i) { swap(&arr[i],&arr[largest]); maxHeapIFY(arr,largest,heapsize); } }/*int maxNum(int *arr){ return arr[1];}*/int heapExactMax(int *arr,int *heapsize){ if(*heapsize<1) exit(0); int max=arr[1]; arr[1]=arr[*heapsize]; *heapsize=*heapsize-1; maxHeapIFY(arr,1,*heapsize); return max;}void heapIncreaseKey(int *arr,int i,int key){ if(key<arr[i]) exit(0); arr[i]=key; while(i>1&&arr[PARENT(i)]<arr[i]) { swap(&arr[i],&arr[PARENT(i)]); i=PARENT(i); }}void heapInsertKey(int *arr,int key,int *heapsize){ *heapsize=*heapsize+1; arr[*heapsize]=INT_MIN; heapIncreaseKey(arr,*heapsize,key);}int main(){ int arr[SIZE]={0,1,56,32,4,64,32,53}; //int initLength; int initHeapSize=7; int i=initHeapSize>>1; for(;i>=1;i–) { maxHeapIFY(arr,i,initHeapSize); } /*int max=maxNum(arr); printf(“%d”,max);*/ //int max=heapExactMax(arr,&initHeapSize); //printf(“%d\n”,max); //heapIncreaseKey(arr,3,1000); //heapInsertKey(arr,78,&initHeapSize); int key; while(scanf(“%d”,&key)&&key!=-1) { heapInsertKey(arr,key,&initHeapSize); } int initLength=initHeapSize; int j=initHeapSize; for(;j>=2;j–) { swap(&arr[1],&arr[j]); initHeapSize=initHeapSize-1; maxHeapIFY(arr,1,initHeapSize); } int k=1; for(;k<=initLength;k++) { printf(“%d “,arr[k]); } system(“pause”); return 0;}

，真凉爽啊！青山绿水映入我的眼中，景色怡人啊！