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

0. 前言

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

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

更新紀錄 :

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

1. 堆積

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

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

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

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

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

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

1.1 插入

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

Algorithm 1. 插入元素

例題 1.H\mathcal {H}

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

插入元素 00.

:

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

Figure 2-1. 插入 00

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

Figure 2-2. 第一次上溯

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

Figure 2-3. 第二次上溯

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

\blacksquare

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

1.2 移除

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

Algorithm 2. 移除元素

例題 2.H\mathcal {H}

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

中移除元素 00.

:

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

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

根節點的兩個子節點中的元素 5511 顯然是 11 比較小, 而 11 也比 1212 小, 所以 11 要上溯.

Figure 4-2. 第一次篩選

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

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

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

\blacksquare

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

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

1.3 初始化

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

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

Algorithm 3. 初始化

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

:

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

Figure 5-1. 建立二元樹

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

Figure 5-2. 元素 00 上溯

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

Figure 5-3. 元素 55 上溯

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

Figure 5-4. 元素 00 上溯, 3030 待定

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

Figure 5-5. 堆積建立完成

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

\blacksquare

斷言 1.Algorithm 3 驅動的堆積初始化, 其時間複雜度為 Θ(n)\Theta(n).

證明證明 :

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

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

為了得到總體的時間複雜度, 接下來我們考慮數列 xn=(ξn)2n1x_{n} = (\xi - n)2^{n - 1} 的前 nn 項和 SxnS_{x_{n}}. 其中, ξ\xi 是任意常數. 直接求解其前 nn 項和是比較困難的, 因此我們考慮求 SxnS_{x_{n}} 的範圍. 顯然, 當 ξ>n\xi > n 時, 有 2n1xnξ2n.\displaystyle {2^{n - 1} \leq x_{n} \leq \xi 2^{n}}. 因此, 我們令 yn=2n1y_{n} = 2^{n - 1}, zn=ξ2nz_{n} = \xi 2^{n}. 我們分別求 yny_{n}znz_{n} 的前 nn 項和 SynS_{y_{n}}SznS_{z_{n}}. 由於 yny_{n}znz_{n} 都是等比數列, 因此有 Syn=2n1,Szn=ξ2n+12ξ.\displaystyle {S_{y_{n}} = 2^{n} - 1, S_{z_{n}} = \xi 2^{n + 1} - 2\xi}. 於是, 我們有 2n1Sxnξ2n+12ξ.\displaystyle {2^{n} - 1 \leq S_{x_{n}} \leq \xi 2^{n + 1} - 2\xi}.

將上面的 nn 使用 h=log2(n+1)h = \left \lceil \log_{2} {(n + 1)} \right \rceil 進行置換, 可得 2log2(n+1)Sxnξ2log2(n+1)2ξ.\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}.2log2(n+1)2log2(n+1)2^{\left \lceil \log_{2} {(n + 1)} \right \rceil} \geq 2^{\log_{2} {(n + 1)}}2log2(n+1)2log2(n+1)+12^{\left \lceil \log_{2} {(n + 1)} \right \rceil} \leq 2^{\log_{2} {(n + 1)} + 1}, 於是有 n+1Sxn2ξ(n+1)2ξ.\displaystyle {n + 1 \leq S_{x_{n}} \leq 2\xi(n + 1) - 2\xi}.SxnS_{x_{n}} 顯然是堆積初始化的時間複雜度, 於是根據《漸近分析基礎》中的定義 3, 即 Θ 記法的定義, 以 Algorithm 3 驅動的堆積初始化演算法的時間複雜度為 Θ(n)\Theta(n).

\blacksquare

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

2. 堆積排序法

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

Algorithm 4. 堆積排序法

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

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

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

3. 優先佇列

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

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

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

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

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

4. 實作

Code 1. 向堆積中插入元素
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; }
Code 2. 從堆積中移除元素
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; }
Code 3. 初始化堆積
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; } }
Code 4. 堆積排序法
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, 大家可以參考後自行實作.