在數據結構中，堆其實就是一棵完全二叉樹。我們知道內存中也有一塊叫做堆的存儲區域，但是這與數據結構中的堆是完全不同的概念。在數據結構中，堆分為大根堆和小根堆，大根堆就是根結點的關鍵字大于等于任一個子節點的關鍵字，而它的左右子樹又分別都是大根堆；小根堆與大根堆恰好相反。在C++的STL中優先隊列priority_queue結構就是實現的堆結構。下來自己動手現實一個堆結構，包括heap_init,heap_insert,heap_top等操作。
1、堆的實現
因為堆是一棵完全二叉樹，所以我們可以用順序表來實現，而且堆也只能用順序表。我們用vector。
(1) 堆的初始化
對堆的初始化基本思想：首先初始數組是一個雜亂無章的序列，但是如果堆中只有一個元素heap[0]，那么heap[0]本身是一個堆，然后加入heap[1]調整堆；繼續加入heap[2].....直到完成所有元素的調整。
void sift_up(vector<int> &heap,int index){while((index+1)/2-1 >= 0){if(heap[(index+1)/2-1] < heap[index]){swap(&heap[(index+1)/2-1],&heap[index]);index = (index+1)/2-1;}elsebreak;} }void heap_init(vector<int> &heap){if(heap.empty())return ;for(int i=1; i<heap.size(); i++){sift_up(heap,i);} }
(2) 向堆中插入元素
把插入的元素放入堆的末尾，然后向上調整堆。
void heap_insert(vector<int> &heap,int element){heap.push_back(element);sift_up(heap,heap.size()-1); }
(3) 取出堆頂的元素
取出一個元素后，用最后一個元素填補第一個元素的位置，然后向下依次調整堆。
void sift_down(vector<int> &heap,int index){while(index*2+2 < heap.size()){if(heap[index*2+1]>=heap[index*2+2] && heap[index]<heap[index*2+1]){swap(&heap[index],&heap[index*2+1]);index = index*2+1;}else if(heap[index*2+1]<heap[index*2+2] && heap[index]<heap[index*2+2]){swap(&heap[index],&heap[index*2+2]);index = index*2+2;}elsebreak;} } bool heap_top(vector<int> &heap,int *res){if(heap.empty())return false;*res = heap[0];heap[0] = heap[heap.size()-1];heap.erase(heap.end()-1);sift_down(heap,0);return true; }
2、堆排序
首先初始化堆，然后依次取出堆頂的值。這里為大根堆，所以是從大到小排序。
void heap_sort(vector<int> &vec){heap_init(vec);int len = vec.size();while(len--){int num;heap_top(vec,&num);printf("%d ",num);} }
堆排序的時間復雜度為O(nlog2n)，從上面排序的步驟可以看出它是不穩定的排序。但是它與選擇排序，歸并排序一樣時間復雜度不隨序列的分布變化而變化。而對于插入排序和冒泡排序來說，當輸入序列有序或者基本有序時，它們的復雜度會遞減為O(n)，而快速排序則會退化成O(n2)。
所以在具體應用中，要根據輸入序列來選擇哪種排序方法，具體問題具體分析。由于堆排序特殊的排序結構和優良的性能，所以在很多時候下都可以采用堆排序。
3、堆排序的應用
在一個n個數的序列中取其中最大的k個數（Top k問題）。
這是一個很常見的排序算法題。
方法一：直接對這這n個數進行排序，然后取k個數。時間復雜度最少為O(nlog2n)。
方法二：借鑒快排的思路，并不需要完整地實現快排，只需要實現快排的一部分即可得到最大的k個數。復雜度為O(nlog2k)。
方法三：可以采用哈希排序，先把n中開始的k個數放入hash表中，然后依次從剩下的的n-k個數中取出一個，與hash表中的k個數比較，每次淘汰最小的那個數。時間復雜度為O((n-k)*k)。
方法四：取出n中開始的k個數，建立一個小根堆，然后從剩下的n-k個數中，每次取出一個數插入小根堆中，然后刪除堆頂的那個元素（堆中的最小值）。時間復雜度為O(*(n-k)*lg2k)。
不可否認，采用堆來求最大的k個數性能是最好的，但是好處還不止這么一點點！！我們試想一下，如果輸入的序列很大，也就是n值很大，以致于無法全部存放在內存中，那么這時候，方法一和方法二就不管用了，當然方法一采用歸并排序可以達到目的，但是這時候需要多少次IO？？。如果選擇方法四，最多只需要(n-k)次IO，當然方法三也是如此，只是每次需要比較k次。
完整代碼詳見：https://github.com/whc2uestc/DataStructure-Algorithm/tree/master/heap
版權所有，歡迎轉載，轉載請注明出處。
