0. 導論

在合併排序法和快速排序法中, 其時間複雜度達到了排序時間複雜度的下限 \Omega(n\log {n}). 但是, 從空間的角度來說, 不管是使用遞迴來實作還是使用堆疊來消除遞迴, 我們仍然需要 O(n) 的空間來輔助排序的過程. 而在堆積排序中, 我們可以完全在原陣列中進行, 於是空間複雜度便為 O(1). 對於時間複雜度, 堆積排序法仍然可以保持 O(n\log {n}). 而堆積排序是以堆積這個資料結構為基礎, 另外一個資料結構優先佇列也是以堆積為基礎的資料結構.

1. 定義

定義 1. (大根樹) 對於一棵樹, 若每一個節點的值都大於其子節點 (若有) 的值, 那麼我們稱這棵樹為大根樹.

定義 1'. (小根樹) 對於一棵樹, 若每一個節點的值都小於其子節點 (若有) 的值, 那麼我們稱這棵樹為小根樹.

由定義, 我們可以推斷, 大根樹和小根樹並不一定是二元樹, 可以是 m 元樹 (m \geq 1). 當向一棵大根樹或者小根樹中插入某個元素的時候, 我們需要將這個元素自下而上地調整到合理的位置, 這個過程我們稱為上溯. 和上溯對應的是下溯.

根據大根樹的定義, 顯然樹中最大的元素必定位於根節點. 否則, 就會出現某個子樹不符合大根樹的定義, 要對這棵子樹的節點進行響應的調整. 對於小根樹來說也是類似, 最小的元素必定位於根節點.

定義 2. (大根堆積) 對於一棵完全二元樹, 若其滿足大根樹的定義, 那麼我們稱其為大根堆積.

定義 2'. (小根堆積) 對於一棵完全二元樹, 若其滿足小根樹的定義, 那麼我們稱其為小根堆積.

大根堆積和小根堆積合稱為堆積. 由於它們都是完全二元樹, 全部元素會按照從上至下從左至右的順序依次排列, 因此最適宜描述存儲堆積的是陣列. 使用陣列存儲堆積時, 若一個堆積有 n 個元素, 那麼前 n 個空間必定不會被浪費. 只需要在陣列空間不夠用的時候, 向後擴張即可.

堆積是我們這一篇文章主要討論的資料結構, 對於大根樹或者小根樹, 大家熟悉定義即可. 不過, 我們主要討論的是大根堆積, 小根堆積不作為主要討論的內容, 因為它可以從大根堆積類似可得. 接下來的文章中, 如果沒有特殊說明, 那麼堆積預設表示著大根堆積.

2. 插入

若一個大根堆積有 n 個元素. 向這個大根堆積插入一個元素的時候, 我們首先將這個元素安排在 n + 1 的位置. 然後比較這個元素和其父節點元素的大小. 如若以陣列來存儲一個大根堆積, 那麼這個元素的父節點必定在第 \left \lfloor \frac {n + 1}{2} \right \rfloor. 如果這個元素比父節點的元素要大, 那麼交換這個兩個元素的位置. 反覆執行上述步驟, 直到這個元素不再比父節點要大或者成為根節點時停止.

若使用 C++ 來描述這個過程, 就可以將程式碼寫為 :

void push_heap(int *begin, int *end) {
    const auto distance {end - begin};
    if(distance < 2) {
        return;
    }
    auto child {distance - 1}, parent {(child - 1) / 2};
    if(begin[parent] > begin[child]) {
        return;
    }
    auto value {begin[child]};
    do {
        begin[child] = begin[parent];
        if(parent == 0) {
            break;
        }
        child = parent;
        --parent /= 2;
    }while(value > begin[parent]);
    begin[parent] = value;
}

這裡的 beginend 是堆積的範圍, end 是要插入的元素而不是尾後疊代器.

現在我們來分析插入操作的時間複雜度. 一個堆積是一棵完全二元樹, 所以其高度 h 必定不大於元素數量 n, 即 h \leq n, 若且唯若 n \leq 2 時等號成立. 如果插入時, 恰好這個位置的父節點比插入的元素要大, 那麼此時不需要任何調整, 那麼時間複雜度為 \Theta(1). 否則, 就要對元素進行上溯, 此時上溯至多進行到根節點, 也就是上溯的次數為樹的高度 h. 因此, 在上溯到根節點這種最壞的情況下, 時間複雜度為 \Theta(h). 故平均情況下, 插入操作的時間複雜度為 \Theta(h).

3. 移除

堆積的移除一般都會被限制, 只允許移除根節點中的元素. 移除的時候我們不是將根節點刪除, 然後重新建立一個根節點, 而是將根節點中的元素刪除並且保留根節點為空, 然後重新組織堆積. 這是因為堆積一般都是使用陣列來存儲的, 而並非連結串列. 即使使用連結串列來存儲, 刪除一個節點而建立一個新的節點所需要的時間也比直接替換元素要快得多. 為了使得這個堆積仍然是完全二元樹, 並且讓操作盡量簡單, 我們提取原本位於第 n 個節點的元素 k. 現在考慮根據元素 k 來重新組織堆積. 我們令 e 表示空的節點 : 首先判定 e 是否存在子節點, 如果不存在, 那麼直接將 k 放入 e 中即可. 否則, 我們設 e 的兩個字節點中最大的元素為 m, 如果 k > m, 那麼就直接將 k 放入 e 中; 如果 m > k (等號是否成立不影響最終結果, 此處我們讓等號不成立), 就讓 m 上溯到其父節點中, 而本身存儲 m 的節點將會置空, 成為新的 e, 重複上述步驟, 直到 k 直接被放入 e 為止.

若使用 C++ 來描述這個過程, 就可以將程式碼寫為 :

void pop_heap(int *begin, int *end) {
    auto distance {end - begin};
    if(distance < 2) {
        return;
    }
    --distance;
    auto value {*--end};
    auto parent {0}, child {1};
    while(true) {
        if(const auto right_child {child + 1}; right_child < distance and begin[right_child] > begin[child]) {
            ++child;
        }
        begin[parent] = begin[child];
        parent = child;
        ++(child *= 2);
        if(child >= distance) {
            break;
        }
    }
    begin[parent] = value;
}

需要注意的是, 函式參數 end 是尾後疊代器, 不同於上面的 push_heap 函式.

堆積的廣義移除不被限制, 可以移除堆積中任意一個元素. 若這個元素不位於根節點, 其實可以看作從一棵子樹中刪除一個根節點, 那麼就執行上面的操作. 但是, 當上面的操作完成時, 並不能直接完成移除. 由於這個子樹位於某個父節點 p 的子節點中, 因此我們還要考察新的根節點中的元素是否比 p 要大. 如果不是, 那麼移除操作就完成了; 否則, 我們還需要像插入一樣, 從新的根節點開始上溯, 直到滿足堆積定義為止, 移除才算是真正完成.

最後, 我們來分析以下移除操作的時間複雜度. 首先討論被限制的移除, 若最後一個元素即是根節點的左子節點或者右子節點, 那麼經過一次比較便可以將提取的元素放入合適的位置. 此時, 所需要的時間為 \Theta(1). 在最壞的情況下, 要進行 h 次比較才可以找到合適的位置, 那麼所需要的時間為 \Theta(h). 其中, h 是堆積的高度. 那麼平均情況下的時間複雜度為 \Theta(h).

4. 初始化

最簡單的初始化方法就是一個一個讓元素進入堆積. 如果初始時, 有 n 個元素等待進入堆積, 要將這 n 個元素放入堆積並且維護堆積, 需要耗費 \Theta(n\log {n}) 的時間. 但是實際上, 我們有更快的方法來初始化一個堆積. 我們首先將這 n 個元素建立為一棵完全二元樹, 建立的方式可以按照元素進入的順序, 或者是隨機, 又或者是其它方式 (平均情況下, 這不會影響總的時間複雜度). 那麼一般情況下, 這棵完全二元樹並不是一個堆積, 因為它不滿足堆積的定義. 首先, 我們注意到, 從第 \left \lfloor \frac {i}{2} \right \rfloor + 1 這個位置開始, 接下來的元素都沒有子節點. 因此, 我們並不需要考慮這些元素對應的節點是否需要進行調整, 只需要考慮從第 \left \lfloor \frac {i}{2} \right \rfloor 個元素開始, 以從右到左, 從下至上的順序逐漸向根節點回退, 在這個過程中調整元素的順序. 假設目前處於第 i個節點, 不妨稱為節點 i, 裡面放置著元素 k, 那麼我們檢查以節點 i 為根節點的子樹是否為堆積. 如果不是的話, 就需要對這個完全二元子樹進行調整. 調整的方法是檢查節點 i 的兩個子節點中較大的那個元素是不是比 k 還要大. 如果是的話, 那麼把元素 k 從節點 i 中提取出來, 把子節點中更大的元素放置在節點 i 中. 此時, 子節點中的元素被清除, 子節點為空. 我們現在用 e 表示空的節點. 接著, 不斷檢查 e 兩個子節點, 如果出現子節點元素比 k 要大, 那麼重複上面的操作; 如果兩個子節點比 k 要小, 那麼就將 k 放置在這個位置上, 本次調整便結束了. 調整結束之後, 接著向前檢查第 i - 1 個節點, 直到檢查到根節點為止.

若使用 C++ 來描述這個過程, 就可以將程式碼寫為 :

void make_heap(int *begin, int *end) {
    const auto distance {begin - end};
    for(auto i {(distance - 2) / 2}; i >= 0; --i) {
        auto parent {i};
        auto child {parent * 2 + 1};
        if(const auto right_child {child + 1}; right_child < distance and begin[right_child] > begin[child]) {
            ++child;
        }
        if(begin[parent] > begin[child]) {
            continue;
        }
        auto value {begin[parent]};
        do {
            begin[parent] = begin[child];
            parent = child;
            if(++(child *= 2); child >= distance) {
                break;
            }
            if(const auto right_child {child + 1}; right_child < distance and begin[right_child] > begin[child]) {
                ++child;
            }
        }while(begin[child] > value);
        begin[parent] = value;
    }
}

此處的 end 是尾後疊代器.

斷言 1. 採用上述方法的堆積初始化, 其時間複雜度為 \Theta(n).

證明 :

初始有 n 個元素, 那麼完全二元樹的高度為 h = \left \lceil \log_{2} {(n + 1)} \right \rceil.

我們從第 \left \lfloor \frac {i}{2} \right \rfloor 個元素開始考慮, 而這個元素必定位於第 h - 1 層. 若這個元素比其子節點要小, 那麼子節點中的那個最大的元素要上溯. 此時, 只需要調整一次就可以將這棵子樹變為堆積, 因為這棵子樹的高度為 2. 在同一層的元素的上溯次數至多也是一次, 同時這一層至多又有 2^{h - 1} 個元素. 因此, 調整這一層所需要的時間為 \Theta \left (2^{h - 1} \cdot 1 \right ) = \Theta \left (2^{h - 1} \right ). 在第 h - 2 層時, 總共有 2^{h - 2} 個元素, 以該層元素節點為根節點的子樹的高度為 3, 調整至多進行 2 次. 那麼這一層所需要的時間為 \Theta \left (2^{h - 2} \cdot 2 \right ) = \Theta \left (2^{h - 1} \right ). 類似地, 可以得到第 i 層所需要的時間為 \Theta \left ((h - i)2^{i - 1} \right ). 其中, i = 1, 2, ..., h - 1.

為了得到總體的時間複雜度, 接下來我們考慮數列 x_{n} = (\xi - n)2^{n - 1} 的前 n 項和 S_{x_{n}}. 其中, \xi 是任意常數. 直接求解其前 n 項和是比較困難的, 因此我們考慮求 S_{x_{n}} 的範圍. 顯然, 當 \xi > n 時, 有 \displaystyle {2^{n - 1} \leq x_{n} \leq \xi 2^{n}} 因此, 我們令 y_{n} = 2^{n - 1}, z_{n} = \xi 2^{n}. 我們分別求 y_{n}z_{n} 的前 n 項和 S_{y_{n}}S_{z_{n}}. 由於 y_{n}z_{n} 都是等比數列, 因此有 \displaystyle {S_{y_{n}} = 2^{n} - 1\ \ \ \ \ \ \ \ \ \ S_{z_{n}} = \xi 2^{n + 1} - 2\xi} 於是, 我們有 \displaystyle {2^{n} - 1 \leq S_{x_{n}} \leq \xi 2^{n + 1} - 2\xi}

將上面的 n 使用 h = \left \lceil \log_{2} {(n + 1)} \right \rceil 進行置換, 可得 \displaystyle {2^{\left \lceil \log_{2} {(n + 1)} \right \rceil} \leq S_{x_{n}} \leq \xi 2^{\left \lceil \log_{2} {(n + 1)} \right \rceil} - 2\xi}2^{\left \lceil \log_{2} {(n + 1)} \right \rceil} \geq 2^{\log_{2} {(n + 1)}}2^{\left \lceil \log_{2} {(n + 1)} \right \rceil} \leq 2^{\log_{2} {(n + 1)} + 1}, 於是有 \displaystyle {n + 1 \leq S_{x_{n}} \leq 2\xi(n + 1) - 2\xi}S_{x_{n}} 顯然是堆積初始化的時間複雜度, 於是根據《漸近分析基礎》中的大 Θ 記法的定義, 時間複雜度為 \Theta(n)

\blacksquare

5. 堆積排序法

不難發現, 每一次從堆積中移除根節點元素的時候, 這個元素總是當前堆積中最大或者最小的元素. 因此, 不斷從堆積中移除元素, 直到堆積為空的時候, 便有了一個有序的序列. 這便是堆積排序的基本思想.

我們可以使用 C++ 來描述這一想法 :

void heap_sort(int *begin, int *end, int *out) {
    auto size {end - begin};
    for(auto i {0}; i < size; ++i) {
        *out++ = *begin;
        pop_heap(begin, end);
    }
}

現在, 我們來分析堆積排序的複雜度. 建立一個堆積的時間複雜度為 \Theta(n), 而每一次從堆積中移除一個元素的時間複雜度為 \Theta(n\log {n}). 由於建立堆積和移除元素互不干擾, 因此總體的時間複雜度為 \Theta(n\log {n}). 而最開始的時候, 我們已經說過, 堆積排序的不需要額外的輔助空間, 空間的利用率比快速排序法和合併排序法要高, 為 \Theta(1).

6. 優先佇列

如果限制一個線性序列的移除操作只能在頭部進行, 那麼只要限制插入操作只在尾部, 那麼這便是佇列. 如果這個序列不是線性的, 而是一個堆積, 並且限制移除操作只能在根節點進行, 那麼這個資料結構我們稱為優先佇列.

在作業系統中, 經常使用優先佇列. 例如現在 CPU 要切換到某個程式, 如果有一個優先級更高的程式需要緊急運作, 那麼這個程式的運作就會被延後, 因為作業系統通暢優先選擇位於優先佇列根節點的程式進行運作. C++ 標準樣板程式庫中的標頭檔 <priority_queue> 裡面有一個 std::priority_queue, 這便是一個優先佇列. 它保存了一個陣列, 這個陣列利用和我們上面類似的程式碼被維護為一個堆積. 因為真正的實作函式為 std::make_queue, std::push_heapstd::pop_heap, 因此 std::priority_queue 被實作為一個容器配接器. 內部的容器用於存儲元素, 而真正維護堆積的操作是 std::make_queue, std::push_heapstd::pop_heap.

優先佇列由於完全使用堆積相關的演算法, 所以其操作的時間複雜度和空間複雜度和堆積相同.

7. 實作

本文對於堆積的操作和堆積排序的實作都沒有採用範型程式設計, 如果閣下有興趣, 請移步 :