学步园

今天在图书馆把优先队列好好看了看，还把快排看了个头~感觉不错~~就是图书馆的椅子太硬了。。坐了快俩小时，咯得慌。。。

回来把函数写了下，虽然是参照书的 = = 下次要自己写出来！不过原理已经懂了~~~

我这个是实现优先队列插入，堆的维护，删除，这个是最大优先队列~~

#include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <string.h><br /> using namespace std;<br /> int heapsize = 0;<br /> void MaxHeapIFY(int a[],int i)<br /> {<br /> int left = i*2;<br /> int right = i*2+1;<br /> int largest;<br /> if( left <= heapsize && a[left] > a[i] )<br /> largest = left;<br /> else<br /> largest = i;<br /> if( right <= heapsize && a[right] > a[largest] )<br /> largest = right;<br /> if( largest != i )<br /> {<br /> swap(a[i],a[largest]);<br /> MaxHeapIFY(a,largest);<br /> }<br /> }<br /> void HeapIncreaseKey(int a[],int i,int key)<br /> {<br /> a[i] = key;<br /> int parent = i/2;<br /> while( i>1 && a[parent] < a[i] )<br /> {<br /> swap(a[i],a[parent]);<br /> i = parent;<br /> parent = i/2;<br /> }<br /> }<br /> void MaxHeapInsert(int a[],int key)<br /> {<br /> heapsize++;<br /> a[heapsize] = INT_MIN;// = = 这点不明白呀 晚上问问GB去。。<br /> HeapIncreaseKey(a,heapsize,key);<br /> }<br /> int HeapExtractMax(int a[])<br /> {<br /> int max = a[1];<br /> a[1] = a[heapsize];<br /> heapsize--;<br /> MaxHeapIFY(a,1);<br /> return max;<br /> }<br /> int main(void)<br /> {<br /> int a[11] = {0,0,6,7,8,3,4,2,5,9,1};<br /> for(int i=1; i<=10; i++)<br /> {<br /> MaxHeapInsert(a,a[i]);<br /> }<br /> for(int i=1; i<=10; i++)<br /> printf("%d ",HeapExtractMax(a));<br /> system("pause");<br /> return 0;<br /> }<br />