C++建堆操作

在某些情況下，我們希望使用一個列表的所有元素來構(gòu)建一個堆，這個過程被稱為“建堆操作”。

借助入堆操作實現(xiàn)

我們首先創(chuàng)建一個空堆，然后遍歷列表，依次對每個元素執(zhí)行“入堆操作”，即先將元素添加至堆的尾部，再對該元素執(zhí)行“從底至頂”堆化。

每當一個元素入堆，堆的長度就加一。由于節(jié)點是從頂?shù)降滓来伪惶砑舆M二叉樹的，因此堆是“自上而下”地構(gòu)建的。

設元素數(shù)量為 n ，每個元素的入堆操作使用 O(log?n) 時間，因此該建堆方法的時間復雜度為 O(nlog?n) 。

通過遍歷堆化實現(xiàn)

實際上，我們可以實現(xiàn)一種更為高效的建堆方法，共分為兩步。

1. 將列表所有元素原封不動添加到堆中，此時堆的性質(zhì)尚未得到滿足。
2. 倒序遍歷堆（即層序遍歷的倒序），依次對每個非葉節(jié)點執(zhí)行“從頂至底堆化”。

每當堆化一個節(jié)點后，以該節(jié)點為根節(jié)點的子樹就形成一個合法的子堆。而由于是倒序遍歷，因此堆是“自下而上”地被構(gòu)建的。

之所以選擇倒序遍歷，是因為這樣能夠保證當前節(jié)點之下的子樹已經(jīng)是合法的子堆，這樣堆化當前節(jié)點才是有效的。

值得說明的是，葉節(jié)點沒有子節(jié)點，天然就是合法的子堆，因此無需堆化。如以下代碼所示，最后一個非葉節(jié)點是最后一個節(jié)點的父節(jié)點，我們從它開始倒序遍歷并執(zhí)行堆化。

my_heap.cpp

/* 構(gòu)造方法，根據(jù)輸入列表建堆 */
MaxHeap(vector<int> nums) {
    // 將列表元素原封不動添加進堆
    maxHeap = nums;
    // 堆化除葉節(jié)點以外的其他所有節(jié)點
    for (int i = parent(size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}

復雜度分析

下面，我們來嘗試推算第二種建堆方法的時間復雜度。

• 假設完全二叉樹的節(jié)點數(shù)量為 n ，則葉節(jié)點數(shù)量為 (n+1)/2 ，其中 / 為向下整除。因此需要堆化的節(jié)點數(shù)量為 (n?1)/2 。
• 在從頂至底堆化的過程中，每個節(jié)點最多堆化到葉節(jié)點，因此最大迭代次數(shù)為二叉樹高度 log?n 。

將上述兩者相乘，可得到建堆過程的時間復雜度為 O(nlog?n) 。但這個估算結(jié)果并不準確，因為我們沒有考慮到二叉樹底層節(jié)點數(shù)量遠多于頂層節(jié)點的性質(zhì)。

接下來我們來進行更為準確的計算。為了減小計算難度，假設給定一個節(jié)點數(shù)量為 n ，高度為 ? 的“完美二叉樹”，該假設不會影響計算結(jié)果的正確性。

圖 8-5   完美二叉樹的各層節(jié)點數(shù)量

如圖 8-5 所示，節(jié)點“從頂至底堆化”的最大迭代次數(shù)等于該節(jié)點到葉節(jié)點的距離，而該距離正是“節(jié)點高度”。因此，我們可以將各層的“節(jié)點數(shù)量  $\times$  節(jié)點高度”求和，從而得到所有節(jié)點的堆化迭代次數(shù)的總和。

使用錯位相減法，用下式  $2T\left(?\right)$  減去上式  $T\left(?\right)$  ，可得：

觀察上式，發(fā)現(xiàn)  $T\left(?\right)$  是一個等比數(shù)列，可直接使用求和公式，得到時間復雜度為：

進一步地，高度為 $?$ 的完美二叉樹的節(jié)點數(shù)量為 $n=2^{?+1}?1$ ，易得復雜度為 $O\left(2^{?}\right)=O\left(n\right)$ 。以上推算表明，輸入列表并建堆的時間復雜度為 $O\left(n\right)$ ，非常高效。