優先隊列不是排序陣列
最小優先隊列保存可比較鍵值的多重集合,支援插入及移除一個最小鍵值;空隊列的移除操作回報下溢。鍵值可以相等。二叉最小堆提供這些操作,但不要求整個陣列有序;對相等鍵值,它本身也不保證先進先出。
定義 3.1.1
(二叉最小堆)
使用連續陣列的一基位置 。對 ,其父節點是 ;可能的子節點是 和 ,前提是索引不超過 。若堆不變量成立,該陣列就是最小堆:
索引規則使其形狀為完全二叉樹:每層由左至右填滿。從任一索引沿父節點最終到達 ,由不變量知, 時 是最小值。陣列不必遞增: 是最小堆,雖然 。
概念視角結構
把位置看成二進位字串
把每個位置寫成二進位。位置 是根;位置 的子節點 和 ,就是在 的二進位字串後面加上 或 。父節點 則是刪去最後一位。例如 的父節點是 ,深度 。位置 的深度是位數減一,而深度為 的位置都至少是 。這個對同一棵樹的描述,同時解釋了完全樹形狀和下文使用的對數高度。
假設比較鍵值及陣列存取都需常數時間。以下界限在已分配足夠容量下計算比較和移動;若陣列擴容時需複製全部元素,該分配成本必須另行分析。
插入:向上修補路徑
把新鍵值加到位置 ,再反覆與父節點比較。若嚴格較小,就交換並在父位置繼續;否則停止。相等時不需交換。
定理 3.1.2
(插入保持堆不變量)
設 是最小堆, 是一個鍵值。把 加在末端,並在它嚴格小於父節點時不斷上移,所得結果是一個最小堆,所含的鍵值是原有鍵值連同 。
證明
(沿向上路徑的迴圈不變量)
令 為目前存放 的位置。斷言:(i) 所有不以 為終點的父子邊都符合不變量;(ii) 若 有父節點 ,則對 的每個子節點 都有 。起初 是葉節點,所以 (ii) 為空,而所有舊邊都有序。
若 或 ,迴圈停止,唯一可能出錯的邊(以 為終點的邊)已有序,所以陣列是堆。否則 ,我們交換。新邊 有序,因為 。對 的子節點 ,由 (ii) 知 ,所以邊 有序。對 的兄弟 ,由舊邊 得 ,所以邊 有序。最後, 現在位於 。設 為 的父節點(若存在)。舊邊 給出 ,而 ,所以 不大於 的兩個子節點,這就是 處的 (ii);仍可能出錯的只有以 為終點的邊。位置每步遞減,所以迴圈會結束。交換保留多重集合,而附加操作保留完全樹形狀。
例題 3.1.3
(把 1 插入六項的堆)
把 插入 。先加在位置 ,與 交換,再與 交換:
鍵值停在根,即位置 。多重集合是原來的加上 。
移除最小值:向下修補路徑
若 ,返回唯一元素並清空陣列。若 ,儲存並返回根,把最後鍵值移到位置 ,並把陣列縮短一項。之後只要目前節點有比它小的子節點,就與較小的子節點交換;兩者相等可任選。然後從該子節點原位置繼續。到達葉節點或目前鍵值不大於任何現有子節點時停止。
定理 3.1.4
(移除最小值)
設 是最小堆,。上述程序返回一個最小鍵值,並留下一個存放其餘 個鍵值的最小堆。
證明
(沿向下路徑的迴圈不變量)
返回的根是最小值,因為由不變量知對所有 都有 。把最後鍵值 移到位置 後,根的兩個子樹仍是堆。令 為存放 的位置。斷言:(i) 所有不以 為起點的邊都有序;(ii) 若 有父節點 ,則對 的每個子節點 都有 。起初 ,所以 (ii) 為空。
若 沒有比 小的子節點,從 出發的邊都有序,陣列是堆。否則令 為 的一個較小子節點,即 ,且對另一個子節點 有 。交換後,邊 有序,因為由 (ii) 知 ; 有序,因為 ; 有序,因為 。 的子節點 在舊陣列中滿足 ,這表示 處的新值不大於 ,所以 (ii) 在 處成立,可能出錯的只有從 出發的邊。每步位置下降一層,所以迴圈在葉節點或停止判斷處結束。移除最後位置保留完全樹形狀。
證明透視
為何必須選較小的子節點
關鍵步驟是選擇較小的子節點 。證明中只有一個不等式用到它: 令交換後通往兄弟的邊有序,其餘部分對任一子節點都成立。條件 (ii) 保證 上方的邊安全:新值 來自 之下,所以至少是 。迴圈會結束,因為位置嚴格增加;它在被移動的鍵值到達葉節點,或沒有子節點更小時完結。相等的情況不需特別處理,因為任一子節點都滿足 。
反例模式
與較大的子節點交換
斷言:刪除時,只要與任何比被移動鍵值小的子節點交換即可。取堆 並移除最小值。最後鍵值 移到根,得到 ,兩個子節點都小於 。與較大的子節點 交換,得到 。位置 是葉節點,迴圈停止,但根 大於其子節點 :結果不是堆。與較小的子節點 交換,得到 ;位置 沒有子節點,且 、,所以這是堆。規則必須指明較小的子節點,這樣上移的鍵值才不大於其兄弟。
例題 3.1.5
(在該插入之後移除最小值)
從 移除最小值,返回 ,並把最後鍵值 移到根,得到 。較小子節點是 ,交換一次得到 。此時 在位置 ,其唯一子節點 較大,所以迴圈停止。
高度與操作成本
定理 3.1.6
(對數高度與成本)
有 個元素的堆,高度至多為 。插入至多交換 次。移除至多交換 次,至多訪問 個位置,每個位置至多作兩次鍵值比較。
證明
(逐層計數)
在深度 的索引均至少為 ,這由二進位字串的描述可見。索引至多為 ,所以 ,即 。插入從位置 開始,其深度至多為 ,每次交換上移一層。 時,移除作用於 個元素,其高度至多為 ;它從根開始,每次交換下移一層。在每個訪問的位置,先比較兩個子節點,再把較小者與該鍵值比較。有效陣列佔用 空間。
令 為操作前大小,在上述容量假設下,每次操作因此耗時 。非空堆只讀最小值需 。這些是上述操作的界限,並未證明特定批量建堆方法或穩定的優先次序。
例題 3.1.7
(相等鍵值與只有一項的堆)
從 移除最小值。儲存 ,把最後鍵值 移到根並縮短陣列:。根有較小的子節點 ,交換得 ,是堆。再把 插入 :加在位置 得 ;其父節點(位置 )是 ,新鍵值並非嚴格較小,所以不交換。邊界情況 :移除時返回唯一鍵值並留下空陣列;對空陣列則回報下溢。
常見錯誤
(以為第二小的鍵值在位置 2)
只有 保證是最小值。在堆 中,位置 是 ,但第二小的鍵值是 ,在位置 。不變量只把每個鍵值與其父節點比較,所以根的兩個子節點之間並沒有次序。
常見錯誤
(零基陣列使用一基的子節點公式)
零基位置時, 的子節點是 和 。若仍用 和 ,位置 會成為自己的子節點,位置 的子節點會是 和 ,而非正確的 和 。應先固定一種約定,再由它推導父節點和子節點公式。
習題與解答
快速檢查
(檢查不變量。 是最小堆嗎?)
把每個位置與其父節點比較。
解答 · 答案
不是:位置 的鍵值 大於其位置 的子鍵值 。
快速檢查
(相等鍵值。 可以是最小堆嗎?)
不變量要求哪些比較?
解答 · 答案
可以。兩個父子比較均非嚴格,兩份最小值可任取其一先移除。
快速檢查
(刪除。用上述方法從 移除最小值。)
先把最後鍵值移到根。
解答 · 答案
把 移到根得到 ;與較小子節點 交換,得到 。
快速檢查
(下溢。從空堆移除時應怎樣?)
有沒有根鍵值可返回?
解答 · 答案
回報下溢,因為沒有根鍵值可返回。一項的情況則返回該鍵值並留下空堆。