堆常用來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，在這種隊(duì)列中，待刪除的元素為優(yōu)先級(jí)最高（最低）的那個(gè)。在任何時(shí)候，任意優(yōu)先元素都是可以插入到隊(duì)列中去的，是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱
一、堆的定義
最大（最小）堆是一棵每一個(gè)節(jié)點(diǎn)的鍵值都不小于（大于）其孩子（如果存在）的鍵值的樹。大頂堆是一棵完全二叉樹，同時(shí)也是一棵最大樹。小頂堆是一棵完全完全二叉樹，同時(shí)也是一棵最小樹。
注意：
- 堆中任一子樹亦是堆。
- 以上討論的堆實(shí)際上是二叉堆(Binary Heap)，類似地可定義k叉堆。
下圖分別給出幾個(gè)最大堆和最小堆的例子：
二、支持的基本操作
堆支持以下的基本操作:- build: 建立一個(gè)空堆；
- insert: 向堆中插入一個(gè)新元素；
- update：將新元素提升使其符合堆的性質(zhì)；
- get：獲取當(dāng)前堆頂元素的值；
- delete：刪除堆頂元素；
- heapify：使刪除堆頂元素的堆再次成為堆。
某些堆實(shí)現(xiàn)還支持其他的一些操作，如斐波那契堆支持檢查一個(gè)堆中是否存在某個(gè)元素。
三、堆的應(yīng)用
1.堆排序
堆排序(HeapSort)是一樹形選擇排序。
堆排序的特點(diǎn)是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系【參見二叉樹的順序存儲(chǔ)結(jié)構(gòu)】，在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。
優(yōu)點(diǎn)直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進(jìn)行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實(shí)上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時(shí)未保留這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作。
堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。
堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無(wú)序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡(jiǎn)單。
（1）、用大根堆排序的基本思想
- 先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始的無(wú)序區(qū)
- 再將關(guān)鍵字最大的記錄R[1](即堆頂)和無(wú)序區(qū)的最后一個(gè)記錄R[n]交換，由此得到新的無(wú)序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key
- 由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由此得到新的無(wú)序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。直到無(wú)序區(qū)只有一個(gè)元素為止。
（2）、大根堆排序算法的基本操作：
- 初始化操作：將R[1..n]構(gòu)造為初始堆；
- 每一趟排序的基本操作：將當(dāng)前無(wú)序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個(gè)記錄交換，然后將新的無(wú)序區(qū)調(diào)整為堆(亦稱重建堆)。
注意：
- 只需做n-1趟排序，選出較大的n-1個(gè)關(guān)鍵字即可以使得文件遞增有序。
- 用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時(shí)刻，堆排序中無(wú)序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為止。
（3）、算法實(shí)現(xiàn) - ////////////////////////////////////////////////////////////////////
- //堆排序
- template <class T>
- void Sort::HeapSort(T arr[], int len){
- int i;
-
- //建立子堆
- for(i = len / 2; i >= 1; i--){
- CreateHeap(arr, i, len);
- }
-
- for(i = len - 1; i >= 1; i--){
- buff = arr[1];
- arr[1] = arr[i + 1];
- arr[i + 1] = buff;
-
- CreateHeap(arr, 1, i);
- }
- }
-
-
- //建立堆
- template <class T>
- void Sort::CreateHeap(T arr[], int root, int len){
- int j = 2 * root; //root's left child, right (2 * root + 1)
- T temp = arr[root];
- bool flags = false;
-
- while(j <= len && !flags){
- if(j < len){
- if(arr[j] < arr[j + 1]){ // Left child is less then right child
- ++j; // Move the index to the right child
- }
- }
-
- if(temp < arr[j]){
- arr[j / 2] = arr[j];
- j *= 2;
- }else{
- flags = true;
- }
- }
- arr[j / 2] = temp;
- }
2.選擇前k個(gè)最大（最小）的數(shù)
思想：在一個(gè)很大的無(wú)序數(shù)組里面選擇前k個(gè)最大（最小）的數(shù)據(jù)，最直觀的做法是把數(shù)組里面的數(shù)據(jù)全部排好序，然后輸出前面最大（最小）的k個(gè)數(shù)據(jù)。但是，排序最好需要O(nlogn)的時(shí)間，而且我們不需要前k個(gè)最大（最小）的元素是有序的。這個(gè)時(shí)候我們可以建立k個(gè)元素的最小堆(得出前k個(gè)最大值)或者最大堆(得到前k個(gè)最小值)，我們只需要遍歷一遍數(shù)組，在把元素插入到堆中去只需要logk的時(shí)間，這個(gè)速度是很樂觀的。利用堆得出前k個(gè)最大（最小）元素特別適合海量數(shù)據(jù)的處理。
代碼：
- typedef multiset<int, greater<int> > intSet;
- typedef multiset<int, greater<int> >::iterator setIterator;
-
- void GetLeastNumbers(const vector<int>& data, intSet& leastNumbers, int k)
- {
- leastNumbers.clear();
-
- if(k < 1 || data.size() < k)
- return;
-
- vector<int>::const_iterator iter = data.begin();
- for(; iter != data.end(); ++ iter)
- {
- if((leastNumbers.size()) < k)
- leastNumbers.insert(*iter);
-
- else
- {
- setIterator iterGreatest = leastNumbers.begin();
-
- if(*iter < *(leastNumbers.begin()))
- {
- leastNumbers.erase(iterGreatest);
- leastNumbers.insert(*iter);
- }
- }
- }
- }
轉(zhuǎn)載請(qǐng)注明：http://www.software8.co/wzjs/cpp/