摘要訊息 : 從一個資料結構導出一種高效的排序演算法.

目錄 隱藏
0. 前言
1. 堆積
1.1 插入
1.2 移除
1.3 初始化
2. 堆積排序法
3. 優先佇列
4. 實作

0. 前言

我們在《複雜度下界》中證明了基於比較的排序演算法的時間複雜度起碼為 \Omega(n\log {n}). 在這一點上, 快速排序法 (《【演算法】快速排序法 (Quick Sort)》) 的一般情形和合併排序法 (《【演算法】合併排序法 (Merge Sort)》) 都可以達到 \Theta(n\log {n}) 這樣的複雜度. 然而, 這兩個排序演算法使用了分而治之的思想, 從而導致它們的空間複雜度起碼都是 O(\log {n}) 級別的. 那麼我們自然就提出疑問 : 是否存在一種基於比較的排序演算法, 不論什麼情況下其時間複雜度都嚴格地為 \Theta(n\log {n}), 並且同時空間複雜度為 \Theta(1)?

本文中將從一種特殊的完全二元樹 (《【資料結構】樹——二元樹》定義 3) 開始研究, 導出一種基於比較的排序演算法, 使得其時間複雜度為 \Theta(n\log {n}) 並且空間複雜度為 \Theta(1).

更新紀錄 :

  • 2022 年 6 月 17 日進行第一次更新和修正.

1. 堆積

定義 1. 對於一棵樹 \mathcal {T}, 若每一個節點中的元素都大於其子節點 (若存在) 中的元素, 那麼我們稱 \mathcal {T} 為最大樹 (maximum tree); 若每一個節點中的元素都小於其子節點 (若存在) 中的元素, 那麼我們稱 \mathcal {T} 為最小樹 (minimum tree).

向最大樹或者最小樹的某個節點下插入元素之後, 必須判斷該元素和節點中元素的大小. 如果不符合最大樹或者最小樹的定義, 那麼可以選擇讓元素上溯 (uptrace) 或者下溯 (downtrace), 將元素插入當前節點的父節點, 或者稱為當前節其中一個子節點的子節點.

根據定義 1, 我們可以知道, 對於任意最大樹或者最小樹, 其根節點中的元素必定是整棵樹中最大或者最小的元素.

定義 2. 若一棵完全二元樹 \mathcal {T} 是最大樹, 那麼稱 \mathcal {T} 為大根堆積 (maximum heap); 若 \mathcal {T} 為最小樹, 那麼稱 \mathcal {T} 為小根堆積 (minimum heap).

大根堆積和小根堆積合稱為堆積 (heap). 由於它們都是完全二元樹, 全部元素會按照從上至下從左至右的順序依次排列, 中間不會存在空隙, 因此最適合儲存堆積的低層資料結構是向量 (《【資料結構】向量 (順序表)》).

接下來討論的堆積如果沒有作特殊說明, 那麼預設是小根堆積.

1.1 插入

若一個堆積有 n 個元素, 那麼向堆積中插入一個元素首先要將這個元素安排在第 n + 1 個位置. 接下來, 檢查該元素父節點, 即第 \left \lfloor \frac {n + 1}{2} \right \rfloor 個節點中的元素是否比插入的元素要大. 如果該元素比父節點中的元素要小, 那麼就需要上溯, 即交換這兩個節點. 此時, 這個元素被安排到了第 \left \lfloor \frac {n + 1}{2} \right \rfloor 個位置. 現在還需要繼續檢查父節點中元素的大小, 直到找到一個父節點, 其元素比插入元素要小或者新插入的元素稱為堆積的根節點為止.

Algorithm 1. 插入元素

例題 1. 向 \mathcal {H}

Figure 1. 小根堆積 \mathcal {H}

插入元素 0.

解 :

首先將 0 安排第一個空的位置, 也就是元素 30 之後.

Figure 2-1. 插入 0

我們發現, 0 的父節點中的元素 12 比 0 要大, 因此 0 需要上溯.

Figure 2-2. 第一次上溯

上溯之後, 由於父節點中的元素 1 仍然比 0 要大, 所以要繼續上溯.

Figure 2-3. 第二次上溯

現在, 我們發現 0 代表的節點已經成為了 \mathcal {H} 的根節點, 所以插入完成.

\blacksquare

如果一個堆積中有 n 個節點, 那麼根據《【資料結構】樹——二元樹》性質 3, 其高度應該是 \left \lceil \log_{2}{n + 1} \right \rceil = \Theta(\log {n}). 因此, 即使新插入的節點上溯到了根節點, 那麼至多也只需要進行 \Theta(\log {n}) 次上溯就可以了. 最終, 向堆積中插入元素的時間複雜度為 \Theta(\log {n}). 而向堆積中插入元素所需要的輔助空間和元素數量無關, 因此向堆積中插入元素的空間複雜度為 \Theta(1).

1.2 移除

堆積的移除一般都會被限制, 只允許移除根節點中的元素. 當然, 也可以允許從任意節點移除. 因為一個堆積對應的二元樹中, 任意子樹也都是一個堆積. 設堆積中有 n 個節點, 由於定義 2 要求堆積應該是一棵完全二元樹, 於是我們考慮使用最後一個節點, 即第 n 個節點來保持這個堆積的有序性. 這裡又可以分為兩種情況. 一種是把最後一個節點拿掉之後, 根節點不再存在任何子節點, 即 n = 2, 那麼這個時候直接讓最後一個節點作為新的節點即可. 另外一種便是 n > 2 的情形. 在 n > 2 的情況之下, 設堆積 \mathcal {H} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \}. 要移除的節點為 \alpha_{1}, 它也是 \mathcal {H} 所對應完全二元樹的根節點. 不過, 我們並不打算直接移除根節點 \alpha_{1}, 而是讓其中的元素置空. 首先考察 \alpha_{1} 的兩個子節點 \alpha_{2} 和 \alpha_{3} 節點中較小的那個元素, 不妨設較小元素對應的節點是 \alpha_{k}. 如果節點 \alpha_{k} 中的元素比 \alpha_{n} 中的元素小, 那麼 \alpha_{k} 中的元素將會上溯到根節點 (注意, 是元素上溯到根節點, 而不是節點上溯, 節點此處不變); 否則, 我們直接將 \alpha_{n} 中的元素放入根節點中並停止移除. 如果移除操作沒有被停止, 那麼接下來比較 \alpha_{k} 的兩個子節點 (若存在) 中的元素, 若這兩個子節點的元素比 \alpha_{n} 中的元素要大, 那麼 \alpha_{k} 這個節點就應該放置 \alpha_{n} 中的元素; 否則, 就讓較小的元素上溯. 不斷重複這個過程, 直到找到 \alpha_{n} 中的元素的合適位置. 在安排好 \alpha_{n} 中的元素之後, \alpha_{n} 這個節點便沒有用了, 因此真正要移除的節點應該是 \alpha_{n} 這個節點.

Algorithm 2. 移除元素

例題 2. 從 \mathcal {H}

Figure 3. 小跟堆積 \mathcal {H}

中移除元素 0.

解 :

我們首先提取出最後一個節點 12 並將根節點置空.

Figure 4-1. 置空根節點並提取最後一個節點

根節點的兩個子節點中的元素 5 和 1 顯然是 1 比較小, 而 1 也比 12 小, 所以 1 要上溯.

Figure 4-2. 第一次篩選

接下來比較原來元素 1 所在節點的兩個子節點. 由於 12 被提取出來了, 所以只有一個子節點, 元素為 30, 比 12 要大. 因此把 12 安排至原來元素 1 所在的節點.

Figure 4-3. 被提取的節點安排到了合適的位置

現在, 只需要回收外面被提取出來的節點, 移除操作就完成了.

\blacksquare

需要注意, 如果從堆積的一顆子樹中移除其根節點, 在根據 Algorithm 2 完成移除操作之後, 還要考察新的子樹根節點是否比其父節點要小. 如果不是, 就需要像插入中那樣進行上溯.

從堆積中移除節點上溯的次數也不會超過 \Theta(\log {n}), 這個和插入是一樣的. 所以從堆積中移除元素的時間複雜度為 \Theta(\log {n}). 從堆積中移除元素所需要的輔助空間和元素數量無關, 因此其空間複雜度為 \Theta(1).

1.3 初始化

最簡單的初始化方法就是一個一個讓元素進入堆積. 如果初始時, 有 n 個元素等待進入堆積, 要將這 n 個元素一個一個插入堆積, 需要耗費 \Theta(n\log {n}) 的時間. 但是實際上, 我們有更快的方法來初始化一個堆積.

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

Algorithm 3. 初始化

例題 3. 將元素 \left \{ 30, 22, 13, 12, 5, 1, 0 \right \} 建立為一個堆積.

解 :

首先, 根據元素順序建立一棵完全二元樹 :

Figure 5-1. 建立二元樹

從第 \left \lfloor \frac {7}{2} \right \rfloor = 3 個節點開始, 之後的所有節點都沒有子節點, 所以我們從第三個節點開始調整. 其兩個子節點中的元素較小的為 0, 它也比 13 要小, 因此要上溯.

Figure 5-2. 元素 0 上溯

上溯完成之後, 以 0 為根節點的子樹便是一個堆積. 接下來考慮第二個節點. 同樣地, 我們進行類似的上溯, 有

Figure 5-3. 元素 5 上溯

這樣, 以 5 為根節點的子樹就是一個堆積了. 最後考慮根節點. 其兩個子節點中, 元素 0 較小, 它同時也小於 30, 因此 0 要上溯.

Figure 5-4. 元素 0 上溯, 30 待定

接下來, 原本以 0 為父節點的兩個子節點中, 元素 1 比較小, 它比 30 還要小, 所以 1 要上溯.

Figure 5-5. 堆積建立完成

在 1 上溯之後, 30 便可以安排到原本 1 所在的節點中, 堆積建立完成.

\blacksquare

斷言 1. 以 Algorithm 3 驅動的堆積初始化, 其時間複雜度為 \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}} 顯然是堆積初始化的時間複雜度, 於是根據《漸近分析基礎》中的定義 3, 即 Θ 記法的定義, 以 Algorithm 3 驅動的堆積初始化演算法的時間複雜度為 \Theta(n).

\blacksquare

顯然, 以 Algorithm 3 驅動的堆積初始化所使用的輔助空間和元素數量無關, 所以其空間複雜度為 \Theta(1).

2. 堆積排序法

不難發現, 每一次從堆積中移除根節點元素的時候, 這個元素總是當前堆積中最大或者最小的元素. 因此, 不斷從堆積中移除元素, 直到堆積為空的時候, 便有了一個有序的序列. 這便是堆積排序的基本思想. 不過, 我們一開始便要求找到一個空間複雜度為 \Theta(1) 的基於比較的排序演算法, 所以當我們從堆積中移除最大或者最小元素之後, 我們把它放到原集合的第一個元素. 然後再從堆積中移除次大或者次小的元素, 放入原集合中的第二個. 不斷重複這個過程, 原集合便有序了.

Algorithm 4. 堆積排序法

我們把 Algorithm 4 驅動的排序演算法稱為堆積排序法 (heap sort).

在 Algorithm 4 中, 雖然我們使用了 \mathcal {H}', 但是實際上 \mathcal {H} 中的元素是不斷減少的. 在實際的程式設計中, 我們通常把根節點元素放入到向量的頭部和尾部. 例如我們把根節點元素從堆積中移除之後, 放入到向量的尾部, 那麼剩下屬於堆積的元素就位於第 1 個到第 n - 1 個.

將任意集合建立成一個堆積所需要的時間複雜度為 \Theta(n). 從堆積中移除根節點對應的元素實際上進行了 n - 1 次, 當堆積只剩下一個元素的時候, 就不再需要移除操作了, 直接拿過來合併即可. 而每一次從堆積中移除一個元素的時間複雜度為 \Theta(\log {n}). 由於建立堆積和堆積排序法所要進行操作相互獨立, 所以總體的時間複雜度就是 \Theta(n) + (n - 1)\Theta(\log {n}) = \Theta(n\log {n}). 這便是以 Algorithm 4 驅動的堆積排序法的時間複雜度. 而不論是建立堆積的過程中還是堆積排序演算法進行的過程中, 所需要的輔助空間都和元素數量無關, 因此以 Algorithm 4 驅動的堆積排序法的空間複雜度為 \Theta(1). 堆積排序法的空間利用率遠高於快速排序法和合併排序法!

3. 優先佇列

定義 3. 設向量 \boldsymbol {\mathcal {h}} = \left \{ \alpha_{1}, \alpha_{2}, ..., \alpha_{n} \right \} 儲存的是一個堆積. 若將向量的操作進行限制,

  • 向 \boldsymbol {\mathcal {h}} 必須以 Algorithm 1 驅動;
  • 要從 \boldsymbol {\mathcal {h}} 中移除元素, 一次只能移除一個元素並且移除的元素只能為 \alpha_{1}, 同時移除元素由 Algorithm 2 驅動,

那麼稱向量 \boldsymbol {\mathcal {h}} 為優先佇列 (priority queue).

優先佇列在名稱上和佇列 (《【資料結構】佇列》) 類似. 而從宏觀上來看, 插入操作雖然有所不同, 但是移除操作大體相同, 都是只能從頭部位置移除元素.

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

4. 實作

void push_heap(int *begin, int *end, int value) {
    *end = value;
    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;
}
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;
}
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;
    }
}
void heap_sort(int *begin, int *end) {
    while(begin + 1 not_eq end) {
        make_heap(begin++, end);
    }
}

對於泛型版本的 C++ 實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/heap.hpp. 另外, 我自己還實作了優先佇列 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/priority_queue.hpp, 大家可以參考後自行實作.