C++建堆操作

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

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

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

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

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

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

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

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

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

之所以選擇倒序遍歷，是因?yàn)檫@樣能夠保證當(dāng)前節(jié)點(diǎn)之下的子樹已經(jīng)是合法的子堆，這樣堆化當(dāng)前節(jié)點(diǎn)才是有效的。

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

my_heap.cpp

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

復(fù)雜度分析

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

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

將上述兩者相乘，可得到建堆過程的時(shí)間復(fù)雜度為 O(nlog?n) 。但這個(gè)估算結(jié)果并不準(zhǔn)確，因?yàn)槲覀儧]有考慮到二叉樹底層節(jié)點(diǎn)數(shù)量遠(yuǎn)多于頂層節(jié)點(diǎn)的性質(zhì)。

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

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

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

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

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

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