用 Heap 實作 Priority Queue

Priority Queue

面對同性質的許多筆記錄時 (例如數百位申請獎助學金的學生的學籍資料), 我們會需要一個可以收納這些記錄的大型資料結構。 用 c++ 的術語來說, 這類具收納功能的資料結構都叫做 container。 例如陣列, linked list, 集合, ... 等等都是 containers。

有時候我們最常做的動作, 是從一個 container 當中固定取出其中 「優先順序最高」 少數幾筆資料 (例如根據複雜公式計算出來的獎助優先順序)。 當然我們也可能需要新增資料, 甚至可能改變其中某一筆資料的 「優先順序」。 一個 container (姑且稱之為 PQ), 除收納功能以外, 如果還提供以下功能, 就稱為一個 priority queue:

  1. insert: 新增一筆記錄進入 PQ。
  2. remove: 傳回 「優先順序」最高 的那一筆記錄, 並將它從 PQ 當中刪除。
  3. change: 改變 PQ 裡面一筆記錄的「優先順序」。
  4. is_empty: 查詢 PQ 裡面是否已清空, 沒有任何記錄。

繼續以 c++ 的術語來說, priority queue 其實是一個 abstract class -- 它不像二元樹或 doubly linked list 等等那麼清楚地有明確的結構, 它只是一個抽象的介面 interface。 有許多不同的實際資料結構, 都可以拿來提供上述功能, 也就是說, 我們想實作 implement 出一個 priority queue, 其實有許多資料結構可以用, 例如 unsorted array, sorted array, unsorted linked list, sorted linked list。 請仔細思考用每一種資料結構實作時, 每個功能該如何實作; 各需要多少時間。 然後與下表對一下答案。

insert remove change is_empty search
unsorted array O(1) O(n) srch+O(1) O(1) O(n)
sorted array O(n) O(n) O(n) O(1) O(lg n)
circular sorted array O(n) O(1) O(n) O(1) O(lg n)
unsorted linked list O(1) O(n) srch+O(1) O(1) O(n)
sorted linked list O(n) O(1) O(n) O(1) O(n)

這裡的 "srch+" 表示搜尋的時間。 如果已知要改變優先順序的元素在那裡, srch=0; 否則 srch 就是 search 欄的時間。

circular sorted array 是 sorted array 的改進版, 有點像是 circular queue。 要把它的 search 寫成 O(lg n), 需要一些功夫。

Priority Queue 可以拿來排序。 用下面這個演算法:

    void pqsort() {
        for (i=0; i<n; ++i) pq.insert(data[i]);
        while (! pq.is_empt()) {
            cout << pq.remove();
        }
    }

其實如果你用 sorted array/list 或是 unsorted array/list 來實作上述演算法當中的 priority queue, 那麼上面的 pqsort 其實就變成了 insertion sort 或是 selection sort (Q: 仔細想想看, 那個是那個?) 這個演算法的複雜度很容易算: 兩個迴圈各做 n 次, 所以如果 insert, remove, is_empty 等三個動作之中最耗時的要花 n, 那麼整體所花的時間就是 n^2。

仔細分析 pqsort 的耗時為 O(n * (新增耗時 + 刪除耗時))。 又從上表看出不同的資料結構, 有些新增快/刪除慢, 有些新增慢/刪除快。 天下沒有十全十美的事, 這是權衡取捨的結果。 但是權衡取捨之下, 是否可能設計出一個資料結構, 它的新增耗時與刪除耗時差不多, 雖然都比 O(1) 慢, 但也都比 O(n) 快呢? 如果可以的話, 那麼我們立即就多了一個比 insertion sort 與 selection sort 都快的排序演算法了。

Heap

想要只花 log n 的時間來增/刪/查一筆記錄, 這個資料結構的長相應該與矮胖的樹有關。 Q: 一個具有 n 個 nodes 的 full binary tree, 它的高度是多少? (你學過 big-O, 現在可以拿出來偷懶) 當然記錄的筆數未必那麼剛好是 2 的次方減 1, 如果我們有 38 筆或是 47 筆資料, 會希望放入什麼樣的樹當中呢? 退而求其次, 可以把樹的上面 h-1 層補滿, 然後最下面不足一層的所有 nodes 由左而右依次補滿, 右邊不足處全部放空, 就成為一棵 complete binary tree。 (所以 full binary tree 是 complete binary tree 的特例)

滿足以下兩個條件的資料結構, 稱為 heap:

  1. 外觀是一棵 complete binary tree
  2. 裡面所有元素皆符合 heap condition

所謂 heap property (或稱 heap condition) 是指每個 node 內的資料比它左右兩側 child nodes 內的資料都小 (但左右兩 child nodes 之間並無一定的關係)。 換句話說, 每棵子樹當中, 最小的元素總是在樹根。

雖說 heap 在觀念上是一棵 complete binary tree, 實際上是存在一個陣列當中 -- root 存在 A[1], 接下來將 A[2] 與 A[3] 由左到右依序補滿第二層, 再將 A[4], A[5], A[6], A[7] 由左到右依序補滿第三層, ... Q: A[25] 的兩個 children 是誰? A[93] 的 parent 是誰? 這種儲存方式完全不需要用到指標。

一個 heap 內如果有一個元素 x 的資料值改變, 因而違反了 heap property, 我們可以用下列兩個演算法之一將這個 heap 修復:

  1. upheap: 如果 x 比它的 parent 小, 則應該將它一路往上浮 (與 parent 交換位置), 直到它比新的 parent 大為止。 耗時 O(lg n)。
  2. downheap: 如果 x 比它的 child 大, 則應該將它一路往下沉 (與其中一個 child 交換位置), 直到它比兩個新的 children 都小為止。 究竟應該與左右那一個 child 交換位置呢? 為了要維持交換後的 heap property, 應該與比較小的 child 交換。 耗時 O(lg n)。

如何從 heap 當中移除最小的元素? 把 root 移除, 把整棵樹最右下角的元素搬到 root, 再用 downheap 修復。

如何加入一個 (任意的) 元素到 heap 當中: 加到整棵樹最右下角的空位, 再用 upheap 修復。

[快速建立 heap] 圖案 建立 heap 的動作, 可以逐一 insert 的方式達成, 但是這樣耗時 O(n log n); 這裡介紹比較快的方法。 先把所有元素不分順序直接放入 heap 中。 一開始將整個陣列的後半部看成是一大堆小 heaps, 逐層由下往上建立稍大的 heaps, 最後建立出一個完整的大 heap。 仔細翻譯成程式碼, 發現用 for (i=n/2; i>0; --i) downheap(i) 的順序正好可以達成這個效果。 耗時多少? 最開始的 n/2 個元素各耗時 1; 其次的 n/4 個元素各耗時 2; 再來的 n/8 個元素各耗時 3 ... 共耗時 O(n)

「最小元素放 root」 的 heap, 叫做 min-heap; 「最大元素放 root」 的 heap, 叫做 max-heap。

如上述, 如果 pqsort() 當中所用的資料結構是 heap, 那麼這個排序演算法就叫做 heapsort。 如果我們的 heap 主要只是為了拿來排序, 那麼不如改用 max-heap。 Heap 建立好之後, 最大元素正好在 root (陣列的第一個元素), 把它和最後一個元素對調, 想像 heap 縮小一格, 而排序完畢的陣列正好從尾巴開始逐漸出現。 這樣 heapsort 就變成是 in-place 了。

請在命令列下執行: perl Heap.pm 觀察它的輸出。 首先是建立 heap 的過程, 由下而上, 每完成一層的 downheap, 就將整個 heap 列印一次。 其次是隨意新增幾個元素。 最後將所有元素逐一刪除。 你可以修改程式下方 $data 變數的初始值, 甚至可以改成用亂數產生, 用不同的資料跑跑看。