【42期】盤點那些必問的數(shù)據(jù)結構算法題之二叉堆
程序員的成長之路互聯(lián)網(wǎng)/程序員/技術/資料共享?關注
閱讀本文大概需要 5 分鐘。
來自：juejin.im/post/5b9e6341e51d450e51626374
0 概述
本文要描述的堆是二叉堆。二叉堆是一種數(shù)組對象，可以被視為一棵完全二叉樹，樹中每個結點和數(shù)組中存放該結點值的那個元素對應。樹的每一層都是填滿的，最后一層除外。二叉堆可以用于實現(xiàn)堆排序，優(yōu)先級隊列等。本文代碼地址在 這里。https://github.com/shishujuan/dsalg/tree/master/code/ds/heap1 二叉堆定義
使用數(shù)組來實現(xiàn)二叉堆，二叉堆兩個屬性，其中 LENGTH(A) 表示數(shù)組 A 的長度，而 HEAP_SIZE(A) 則表示存放在A中的堆的元素個數(shù)，其中 LENGTH(A) <= HEAP_SIZE(A)，也就是說雖然 A[0,1,…N-1] 都可以包含有效值，但是 A[HEAP_SIZE(A)-1] 之后的元素不屬于相應的堆。二叉堆對應的樹的根為 A[0]，給定某個結點的下標 i ，可以很容易計算它的父親結點和兒子結點。注意在后面的示例圖中我們標注元素是從1開始計數(shù)的，而實現(xiàn)代碼中是從0開始計數(shù)。#define?PARENT(i)?(?i?>?0???(i-1)/2?:?0)注：堆對應的樹每一層都是滿的，所以一個高度為 h 的堆中，元素數(shù)目最多為 1+2+2^2+…2^h = 2^(h+1) - 1(滿二叉樹)，元素數(shù)目最少為 1+2+…+2^(h-1) + 1 = 2^h。由于元素數(shù)目 2^h <= n <= 2^(h+1) -1，所以 h <= lgn < h+1，因此 h = lgn 。即一個包含n個元素的二叉堆高度為 lgn 。
#define?LEFT(i)?(2?*?i?+?1)
#define?RIGHT(i)?(2?*?i?+?2)
2 保持堆的性質
本文主要建立一個最大堆，最小堆原理類似。為了保持堆的性質，maxHeapify(int A[], int i) 函數(shù)讓堆數(shù)組 A 在最大堆中下降，使得以 i 為根的子樹成為最大堆。void?maxHeapify(int?A[],?int?i,?int?heapSize)在算法每一步里，從元素 A[i] 和 A[left] 以及 A[right] 中選出最大的，將其下標存在 largest 中。如果 A[i] 最大，則以 i 為根的子樹已經(jīng)是最大堆，程序結束。否則，i 的某個子結點有最大元素，將 A[i] 與 A[largest] 交換，從而使i及其子女滿足最大堆性質。此外，下標為 largest 的結點在交換后值變?yōu)?A[i]，以該結點為根的子樹又有可能違反最大堆的性質，所以要對該子樹遞歸調用maxHeapify()函數(shù)。當 maxHeapify() 函數(shù)作用在一棵以 i 為根結點的、大小為 n 的子樹上時，運行時間為調整A[i]、A[left]、A[right] 的時間 O(1)，加上對以 i 為某個子結點為根的子樹遞歸調用 maxHeapify 的時間。i 結點為根的子樹大小最多為 2n/3(最底層剛好半滿的時候)，所以可以推得 T(N) <= T(2N/3) + O(1)，所以 T(N)=O(lgN)。下圖是一個運行 maxHeapify(heap, 2) 的例子。A[] = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1}，堆大小為 10。
{
????int?l?=?LEFT(i);
????int?r?=?RIGHT(i);
????int?largest?=?i;
????if?(l?<=?heapSize-1?&&?A[l]?>?A[i])?{
????????largest?=?l;
????}
????if?(r?<=?heapSize-1?&&?A[r]?>?A[largest])?{
????????largest?=?r;
????}
????if?(largest?!=?i)?{?//?最大值不是i，則需要交換i和largest的元素，并遞歸調用maxHeapify。
????????swapInt(A,?i,?largest);
????????maxHeapify(A,?largest,?heapSize);
????}
}
3 建立最大堆
我們可以知道，數(shù)組 A[0, 1, …, N-1] 中，A[N/2, …, N-1] 的元素都是樹的葉結點。如上面圖中的 6-10 的結點都是葉結點。每個葉子結點可以看作是只含一個元素的最大堆，因此我們只需要對其他的結點調用 maxHeapify() 函數(shù)即可。void?buildMaxHeap(int?A[],?int?n)之所以這個函數(shù)是正確的，我們需要來證明一下，可以使用循環(huán)不變式來證明。循環(huán)不變式：在for循環(huán)開始前，結點 i+1、i+2…N-1 都是一個最大堆的根。初始化：for循環(huán)開始迭代前，i = N/2-1, 結點 N/2, N/2+1, …, N-1都是葉結點，也都是最大堆的根。保持：因為結點 i 的子結點標號都比 i 大，根據(jù)循環(huán)不變式的定義，這些子結點都是最大堆的根，所以調用 maxHeapify() 后，i 成為了最大堆的根，而 i+1, i+2, …, N-1仍然保持最大堆的性質。終止：過程終止時，i=0，因此結點 0, 1, 2, …, N-1都是最大堆的根，特別的，結點0就是一個最大堆的根。
{
????int?i;
????for?(i?=?n/2-1;?i?>=?0;?i--)?{
????????maxHeapify(A,?i,?n);
????}
}
雖然每次調用 maxHeapify() 時間為 O(lgN)，共有 O(N) 次調用，但是說運行時間是 O(NlgN) 是不確切的，準確的來說，運行時間為 O(N)，這里就不證明了，具體證明過程參見《算法導論》。4 堆排序
開始用 buildMaxHeap() 函數(shù)創(chuàng)建一個最大堆，因為數(shù)組最大元素在 A[0]，通過直接將它與A[N-1] 互換來達到最終正確位置。去掉 A[N-1]，堆的大小 heapSize 減1，調用maxHeapify(heap, 0, --heapSize) 保持最大堆的性質，直到堆的大小由N減到1。void?heapSort(int?A[],?int?n)
{
????buildMaxHeap(A,?n);
????int?heapSize?=?n;
????int?i;
????for?(i?=?n-1;?i?>=?1;?i--)?{
????????swapInt(A,?0,?i);
????????maxHeapify(A,?0,?--heapSize);
????}
}
5 優(yōu)先級隊列
最后實現(xiàn)一個最大優(yōu)先級隊列，主要有四種操作，分別如下所示：insert(PQ， key)：將 key 插入到隊列中。
maximum(PQ)：返回隊列中最大關鍵字的元素
extractMax(PQ)：去掉并返回隊列中最大關鍵字的元素
increaseKey(PQ, i, key)：將隊列 i 處的關鍵字的值增加到 key
typedef?struct?PriorityQueue?{最終優(yōu)先級隊列的操作實現(xiàn)代碼如下：
????int?capacity;
????int?size;
????int?elems[];
}?PQ;
/**
?*?從數(shù)組創(chuàng)建優(yōu)先級隊列
?*/
PQ?*newPQ(int?A[],?int?n)
{
????PQ?*pq?=?(PQ?*)malloc(sizeof(PQ)?+?sizeof(int)?*?n);
????pq->size?=?0;
????pq->capacity?=?n;
????int?i;
????for?(i?=?0;?i?capacity;?i++)?{
????????pq->elems[i]?=?A[i];
????????pq->size++;
????}
????buildMaxHeap(pq->elems,?pq->size);
????return?pq;
}
int?maximum(PQ?*pq)
{
????return?pq->elems[0];
}
int?extractMax(PQ?*pq)
{
????int?max?=?pq->elems[0];
????pq->elems[0]?=?pq->elems[--pq->size];
????maxHeapify(pq->elems,?0,?pq->size);
????return?max;
}
PQ?*insert(PQ?*pq,?int?key)
{
????int?newSize?=?++pq->size;
????if?(newSize?>?pq->capacity)?{
????????pq->capacity?=?newSize?*?2;
????????pq?=?(PQ?*)realloc(pq,?sizeof(PQ)?+?sizeof(int)?*?pq->capacity);
????}
????pq->elems[newSize-1]?=?INT_MIN;
????increaseKey(pq,?newSize-1,?key);
????return?pq;
}
void?increaseKey(PQ?*pq,?int?i,?int?key)
{
????int?*elems?=?pq->elems;
????elems[i]?=?key;
????while?(i?>?0?&&?elems[PARENT(i)]?????????swapInt(elems,?PARENT(i),?i);
????????i?=?PARENT(i);
????}
}
參考資料
算法導論第6章《堆排序》
推薦閱讀：
【41期】盤點那些必問的數(shù)據(jù)結構算法題之鏈表
最近開始整理《100期Java面試題匯總》PDF版本，目前整理到第20期，3.6W詞，想獲取的可以先加我微信，后續(xù)整理完會在朋友圈通知如何獲取。長按二維碼，添加我微信
朕已閱?
評論
圖片
表情