概念
性質: 1.堆是一顆完全二叉樹，用數組實現。?
???2.堆中存儲數據的數據是局部有序的。
最大堆：1.任意一個結點存儲的值都大于或等于其任意一個子結點中存儲的值。?
?????2.根結點存儲著該樹所有結點中的最大值。
最小堆：1.任意一個結點存儲的值都小于或等于其惹你一個子結點存儲的值。?
?????2.根結點存儲著該樹所有結點中的最小值。
無論最小堆還是最大堆，任何一個結點與其兄弟結點之間都沒有必然聯系。
?
STL中并沒有把heap作為一種容器組件，heap的實現亦需要更低一層的容器組件（諸如list,array,vector）作為其底層機制。Heap是一個類屬算法，包含在algorithm頭文件中。雖然STL中關于heap默認調整成的是大頂堆，但卻可以讓用戶利用自定義的compare_fuction函數實現大頂堆或小頂堆。heap的低層機制vector本身就是一個類模板，heap基于vector便實現了對各種數據類型（無論基本數據類型還是用戶自定義的數據類型）的堆排（前提是用戶自定義的數據類型要提供比較機制compare_fuction函數）。
STL里面的堆操作一般用到的只有4個。
他們就是
make_heap();、pop_heap();、push_heap();、sort_heap();
他們的頭函數是algorithm
首先是make_heap();
他的函數原型是：
void make_heap(first_pointer,end_pointer,compare_function);
一個參數是數組或向量的頭指針，第二個向量是尾指針。第三個參數是比較函數的名字
。在缺省的時候，默認是大跟堆。（下面的參數都一樣就不解釋了）
作用：把這一段的數組或向量做成一個堆的結構。范圍是(first,last)
然后是pop_heap();
它的函數原型是：
void pop_heap(first_pointer,end_pointer,compare_function);
作用：pop_heap()不是真的把最大（最小）的元素從堆中彈出來。而是重新排序堆。它
把first和last交換，然后將[first,last-1)的數據再做成一個堆。
接著是push_heap()
void pushheap(first_pointer,end_pointer,compare_function);
作用：push_heap()假設由[first,last-1)是一個有效的堆，然后，再把堆中的新元素加
進來，做成一個堆。
最后是sort_heap()
void sort_heap(first_pointer,end_pointer,compare_function);
作用是sort_heap對[first,last)中的序列進行排序。它假設這個序列是有效堆。（當然
，經過排序之后就不是一個有效堆了）
#include<algorithm> #include<cstdio> using namespace std; bool cmp(int a,int b) //比較函數 { return a>b; } int main() { int i,number[20]={29,23,20,22,17,15,26,51,19,12,35,40}; make_heap(&number[0],&number[12]); //結果是:51 35 40 23 29 20 26 22 19 12 17 15 for(i=0;i<12;i++) printf("%d ",number[i]); printf("\n"); make_heap(&number[0],&number[12],cmp); //結果：12 17 15 19 23 20 26 51 22 29 35 40 for(i=0;i<12;i++) printf("%d ",number[i]); printf("\n"); //加入元素8 number[12]=8; //加入后調整 push_heap(&number[0],&number[13],cmp); //結果：8 17 12 19 23 15 26 51 22 35 40 20 for(i=0;i<13;i++) printf("%d ",number[i]); printf("\n"); //彈出元素8 pop_heap(&number[0],&number[13],cmp); //結果：12 17 15 19 23 20 26 51 22 29 35 40 for(i=0;i<13;i++) printf("%d ",number[i]); printf("\n"); sort_heap(&number[0],&number[12],cmp); //結果不用說都知道是有序的了！ for(i=0;i<12;i++) printf("%d ",number[i]); return 0; }
)
