文檔教程教育【免費下載鏈接】CLRS Solutions to Introduction to Algorithms Third Edition項目地址https://gitcode.com/gh_mirrors/clr/CLRS點擊查看免費下載本篇以《算法導論第三版》第 6.5 節(jié)優(yōu)先隊列Priority Queues為核心基于 CLRS Solutions 倉庫的 docs/Chap06/6.5.md 習題解析系統(tǒng)講解用最大堆與最小堆實現優(yōu)先隊列的四大基本操作MAXIMUM / EXTRACT-MAX / INCREASE-KEY / INSERT、最小優(yōu)先隊列的對稱實現、正確性證明與若干工程化優(yōu)化HEAP-DELETE、k 路歸并。讀完你將掌握優(yōu)先隊列從圖示理解到偽代碼實現再到正確性論證的完整鏈路并能直接復現其中全部 9 道習題的解答與復雜度結論。一、優(yōu)先隊列堆上最實用的動態(tài)集合抽象在《算法導論》第 6 章Heapsort的編排中6.1–6.4 小節(jié) 依次介紹了堆的定義、MAX-HEAPIFY 維護堆性質、BUILD-MAX-HEAP 建堆與 HEAPSORT 排序而6.5 節(jié)則是堆最經典的應用場景——優(yōu)先隊列Priority Queue。正如倉庫 mkdocs.yml 的導航配置所示該節(jié)在站點中被命名為6.5 Priority queues對應文檔 docs/Chap06/6.5.md。優(yōu)先隊列與普通隊列的本質區(qū)別在于出隊順序不取決于入隊先后而取決于元素的優(yōu)先級。當優(yōu)先級就是元素本身的值時一個最大堆天然就是一個最大優(yōu)先隊列——堆頂A[1]恒為全局最大元素。CLRS 倉庫用一組目標堆$$ A \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \rangle $$貫穿了習題 6.5-1 與 6.5-2 的全過程演示這也是理解本節(jié)的標準實驗用例。二、優(yōu)先隊列的四大核心操作與復雜度總覽最大優(yōu)先隊列支持四類基本操作本倉庫對應文檔結合 6.2 節(jié) 的 MAX-HEAPIFY 基礎可整理為操作作用復雜度依賴的子過程HEAP-MAXIMUM(A)返回最大元素A[1]$O(1)$無HEAP-EXTRACT-MAX(A)取出并刪除最大元素$O(\lg n)$MAX-HEAPIFYHEAP-INCREASE-KEY(A, i, key)將A[i]增大到key并上浮$O(\lg n)$自底向上交換MAX-HEAP-INSERT(A, key)插入新元素$O(\lg n)$HEAP-INCREASE-KEY所有 $O(\lg n)$ 操作的代價均來自堆的高度 $\lfloor \lg n \rfloor$參考 6.1-2 的推導。下面我們依次拆解 6.5 節(jié) 9 道習題。三、習題 6.5-1HEAP-EXTRACT-MAX 的完整運行過程題目在堆 $A \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \rangle$ 上演示HEAP-EXTRACT-MAX的逐步操作。原始堆形態(tài)如下倉庫給出的五步推演配圖為 docs/img/6.5-1-1.png 至 docs/img/6.5-1-5.png為取出堆頂抽取最大值 15將末尾元素 1 移到堆頂第一次下濾由于 $13 9 1$交換 1 與 13第二次下濾由于 $12 5 1$交換 1 與 12第三次下濾由于 $6 2 1$交換 1 與 6到達葉子位置。該過程本質上是替換堆頂 → 縮小 heap-size → MAX-HEAPIFY 下濾三步與 6.2 節(jié) MAX-HEAPIFY 的遞歸/迭代下濾完全一致單次代價為 $O(\lg n)$。四、習題 6.5-2MAX-HEAP-INSERT 的完整運行過程題目在同樣的堆上演示MAX-HEAP-INSERT(A, 10)的操作。倉庫的推演配圖為 docs/img/6.5-2-1.png 至 docs/img/6.5-2-5.png分為五步原始堆保持 $A \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \rangle$追加哨兵節(jié)點heap-size加一在末尾追加一個值為 $-\infty$ 的節(jié)點這一步的意義詳見習題 6.5-4更新新節(jié)點 key將新節(jié)點值從 $-\infty$ 提升為 10第一次上浮父節(jié)點 key 小于 10交換二者第二次上浮父節(jié)點 key 仍小于 10再次交換直到父節(jié)點不小于 10 為止。插入的代價同樣等于堆的高度即 $O(\lg n)$而HEAP-INCREASE-KEY的循環(huán)在文檔習題 6.5-5中約定為第 4–6 行這正是我們要在下一節(jié)嚴謹論證正確性的過程。五、習題 6.5-3用最小堆實現最小優(yōu)先隊列題目為最小優(yōu)先隊列寫出HEAP-MINIMUM、HEAP-EXTRACT-MIN、HEAP-DECREASE-KEY、MIN-HEAP-INSERT四個過程的偽代碼。最大堆與最小堆完全對稱只需把大于改為小于、把 MAX-HEAPIFY 換成 6.2-2 中定義的 MIN-HEAPIFY。倉庫給出的四段偽代碼如下HEAP-MINIMUM(A) return A[1]HEAP-EXTRACT-MIN(A) if A.heap-size 1 error heap underflow min A[1] A[1] A[A.heap-size] A.heap-size A.heap-size - 1 MIN-HEAPIFY(A, 1) return minHEAP-DECREASE-KEY(A, i, key) if key A[i] error new key is larger than current key A[i] key while i 1 and A[PARENT(i)] A[i] exchange A[i] with A[PARENT(i)] i PARENT(i)MIN-HEAP-INSERT(A, key) A.heap-size A.heap-size 1 A[A.heap-size] ∞ HEAP-DECREASE-KEY(A, A.heap-size, key)與最大優(yōu)先隊列逐一對齊即可得到HEAP-MINIMUM返回最小值HEAP-EXTRACT-MIN取出最小值后以堆末尾元素填補并用MIN-HEAPIFY下濾HEAP-DECREASE-KEY把 key 減小后自底向上與父節(jié)點比較并上浮MIN-HEAP-INSERT先追加一個 $\infty$ 哨兵再調用HEAP-DECREASE-KEY。四個過程的復雜度與最大堆版本一致$O(1)$ 與 $O(\lg n)$。六、習題 6.5-4為什么插入時要先把 key 置為 $-\infty$題目MAX-HEAP-INSERT第 2 行先把新節(jié)點 key 設為 $-\infty$緊接著又要把它提升到期望值為什么要多此一舉倉庫給出的答案簡潔而關鍵In order to pass the guard clause. Otherwise we have to drop the check if $key A[i]$.也就是說HEAP-INCREASE-KEY(A, i, key)開頭有一條守衛(wèi)guard子句if key A[i] error new key is smaller than current key而MAX-HEAP-INSERT中新增節(jié)點的當前位置A[A.heap-size]尚未被賦值或是舊值如果不先用 $-\infty$ 初始化就無法保證新 key 不小于當前值從而無法通過守衛(wèi)。換句話說$-\infty$ 哨兵是讓插入操作能夠復用HEAP-INCREASE-KEY守衛(wèi)語義的代價對稱地MIN-HEAP-INSERT則使用 $\infty$ 以通過HEAP-DECREASE-KEY的守衛(wèi)。七、習題 6.5-5用循環(huán)不變式證明 HEAP-INCREASE-KEY 的正確性題目利用如下循環(huán)不變式論證HEAP-INCREASE-KEY的正確性在while循環(huán)第 4–6 行每次迭代開始時子數組 $A[1..A.heap\text{-}size]$ 滿足最大堆性質唯一的例外可能是$A[i]$ 大于 $A[\text{PARENT}(i)]$即唯一的一處違反?？梢约僭O調用HEAP-INCREASE-KEY時 $A[1..A.heap\text{-}size]$ 已經滿足最大堆性質。倉庫給出標準的三段式證明初始化Initialization調用前 $A$ 是堆只是 $A[i]$ 可能大于其父節(jié)點因為它剛被修改為更大的值而 $A[i]$ 必然大于其子節(jié)點——否則守衛(wèi)子句會失敗、循環(huán)根本不會進入新值大于舊值舊值又大于子節(jié)點。不變式成立。保持Maintenance當我們交換 $A[i]$ 與其父節(jié)點后最大堆性質恢復唯一的違反點轉移到了新的 $A[\text{PARENT}(i)]$它可能大于自己的父節(jié)點。把 $i$ 更新為其父節(jié)點后不變式對下一輪迭代依然成立。終止Termination循環(huán)在堆被耗盡$i 1$或 $A[i]$ 與父節(jié)點之間滿足最大堆性質時終止。循環(huán)結束時$A$ 是一個最大堆。這個證明模式初始化 / 保持 / 終止與 6.4-2 對 HEAPSORT 的循環(huán)不變式證明 一脈相承是分析上浮式堆操作正確性的標準模板。八、習題 6.5-6借鑒 INSERTION-SORT 內循環(huán)把三次賦值降為一次題目HEAP-INCREASE-KEY第 5 行的每次交換exchange通常需要三次賦值請借鑒INSERTION-SORT內循環(huán)的思想把每次迭代的三次賦值減少到一次。INSERTION-SORT的內循環(huán)并不真正交換而是不斷把較大的元素向后搬移、最后一次性落位。把這一思想移植到堆的上浮過程HEAP-INCREASE-KEY(A, i, key) if key A[i] error new key is smaller than current key while i 1 and A[PARENT(i)] key A[i] A[PARENT(i)] i PARENT(i) A[i] key這樣每輪迭代只執(zhí)行一次賦值A[i] A[PARENT(i)]最終再一次性寫入A[i] key消除了交換所需的三次賦值中的兩次。從常數因子的角度看這是堆操作實現中常見的微優(yōu)化與 6.2-5 把遞歸 MAX-HEAPIFY 改為迭代 屬于同一類優(yōu)化思路。九、習題 6.5-7用優(yōu)先隊列實現 FIFO 隊列與棧題目說明如何用優(yōu)先隊列分別實現先進先出隊列FIFO與棧第 10.1 節(jié)定義了這兩種數據結構。倉庫給出的思路非常直觀棧LIFO每次插入賦予遞增的優(yōu)先級——把新元素優(yōu)先級設為 $\text{HEAP-MAXIMUM}(A) 1$。后入棧的元素優(yōu)先級最高永遠最先被EXTRACT-MAX取出隊列FIFO每次插入賦予遞減的優(yōu)先級——需要維護一個計數器每次插入時遞減。先入隊的元素優(yōu)先級最高因此最先出隊。倉庫同時指出了兩個重要缺陷Both are not very efficient. Furthermore, if the priority can overflow or underflow, so will eventually need to reassign priorities.其一這種做法并不高效每次都依賴堆操作與全局最大/最小值的維護其二若優(yōu)先級可溢出或下溢則最終需要重新分配reassign全部優(yōu)先級。換言之該實現更多是理論可行性的演示而非工程推薦方案。十、習題 6.5-8HEAP-DELETE 的 $O(\lg n)$ 實現與一個典型錯誤題目HEAP-DELETE(A, i)刪除堆 $A$ 中節(jié)點 $i$ 的元素給出一個在 $n$ 元素最大堆上運行時間為 $O(\lg n)$ 的實現。倉庫給出的正確版本如下HEAP-DELETE(A, i) if A[i] A[A.heap-size] A[i] A[A.heap-size] MAX-HEAPIFY(A, i) else HEAP-INCREASE-KEY(A, i, A[A.heap-size]) A.heap-size A.heap-size - 1其正確性關鍵在于分情況討論用堆末尾元素 $A[A.heap\text{-}size]$ 替換被刪節(jié)點后若新值小于原值則可能違反父不小于子的性質需要MAX-HEAPIFY下濾若新值大于原值則可能違反子不大于父的性質需要HEAP-INCREASE-KEY上浮。兩種修復路徑都是 $O(\lg n)$因此整體為 $O(\lg n)$。倉庫特別附帶了一個反例警告不要使用下面這種看起來合理但錯誤的寫法直接替換 MAX-HEAPIFYHEAP-DELETE(A, i) A[i] A[A.heap-size] A.heap-size A.heap-size - 1 MAX-HEAPIFY(A, i)反例對已是最大堆的 $A [15, 7, 9, 1, 2, 3, 8]$ 刪除 $A[5] 2$。刪除前堆結構為15 / \ 7 9 / \ / \ 1 2 3 8錯誤算法用末尾元素 8 覆蓋 2 并下濾后得到15 / \ 7 9 / \ / 1 8 3此時 $8 7$違反了最大堆性質右子樹根 7 比其左孩子 8 更小。原因正是沒有考慮新值大于原值時應上浮這一分支——可見對稱地處理上浮/下濾是這類刪除實現的關鍵。十一、習題 6.5-9用最小堆做 k 路歸并$O(n\lg k)$ 排序合并題目給出一個 $O(n\lg k)$ 時間的算法將 $k$ 個有序列表合并為一個有序列表其中 $n$ 是所有輸入列表的元素總數提示用最小堆做 k 路歸并。這是優(yōu)先隊列最著名的應用之一——k 路歸并k-way merge。倉庫給出的算法描述為從每個列表中取出一個元素放入最小堆同時記錄該元素來自哪個列表每次從堆中取出最小元素并從它所屬的列表中補入下一個元素除非該列表已空重復直至堆為空?？偣灿?$n$ 步每一步對大小為 $k$ 的堆做一次插入或提取代價為 $\lg k$因此總復雜度為 $O(n\lg k)$。倉庫給出的偽代碼如下def MERGE-SORTED-LISTS(lists) n lists.length // Take the lowest element from each of lists together with an index of the list and make list of such pairs. // Pairs are of type (element-value, index-of-list) let lowest-from-each be an empty array for i 1 to n add (lists[i][0], i) to lowest-from-each delete lists[i][0] // This makes min-heap from list lowest-from-each. // We are assuming that pairs of type (element-value, index-of-list) are compared according to the values of elements. A MIN-HEAP(lowest-from-each) let merged-lists be an empty array while not A.EMPTY() element-value, index-of-list HEAP-EXTRACT-MIN(A) add element-value to merged-lists if lists[index-of-list].length 0 MIN-HEAP-INSERT(A, (lists[index-of-list][0], index-of-list)) delete lists[index-of-list][0] return merged-lists該過程復用了本文第五節(jié)實現的HEAP-EXTRACT-MIN與MIN-HEAP-INSERT是優(yōu)先隊列從抽象數據結構走向真實排序算法的經典落點。十二、倉庫中的配套資料與延伸閱讀本節(jié)內容在 CLRS Solutions 倉庫中的完整落點為 docs/Chap06/6.5.md其直接前置章節(jié)包括6.1 Heaps堆的定義、高度 $\lfloor\lg n\rfloor$、葉子下標 $\lfloor n/2\rfloor 1 \sim n$ 等基礎性質6.2 Maintaining the heap propertyMAX-HEAPIFY / MIN-HEAPIFY 及迭代式實現6.5-1 的下濾步驟直接依賴它6.3 Building a heap 與 6.4 The heapsort algorithm建堆與排序構成優(yōu)先隊列操作的完整前置知識章節(jié)問題 6-2d 叉堆把二元堆推廣為 d 元堆EXTRACT-MAX / INSERT / INCREASE-KEY 的復雜度變?yōu)?$O(d\log_d n)$ 與 $O(\log_d n)$可作為本節(jié)操作復雜度的進階練習章節(jié)問題 6-3Young 矩陣利用類似 MAX-HEAPIFY 的下濾思想在 $m\times n$ 矩陣上實現 $O(mn)$ 的 EXTRACT-MIN / 插入 / 排序。整個倉庫以 Markdown KaTeX 編寫由 MkDocs 與 Material for MkDocs 構建為靜態(tài)站點見 README.md 與 mkdocs.yml 中的 KaTeX 與主題配置所有數學公式均以標準 LaTeX 語法渲染便于在移動端與桌面端閱讀。贊分享文檔教程教育【免費下載鏈接】CLRS Solutions to Introduction to Algorithms Third Edition項目地址https://gitcode.com/gh_mirrors/clr/CLRS點擊查看免費下載相關推薦Swift Algorithm Club 優(yōu)先隊列Priority Queue完全指南基于堆的 Swift 實現與實戰(zhàn)Swift Algorithm Club 優(yōu)先隊列Priority Queue完全指南基于堆的 Swift 實現與實戰(zhàn) 優(yōu)先級隊列Priority Qu示例工程教程最大堆上的優(yōu)先隊列全解CLRS 第 6.5 節(jié)習題精講與 C 實現剖析最大堆上的優(yōu)先隊列全解CLRS 第 6.5 節(jié)習題精講與 C 實現剖析 本文以《算法導論》Introduction to Algorithms第 6.文檔教程示例工程OpenBao 的 Priority Queue 實現基于 container/heap 的插件級優(yōu)先隊列sdk/queue 深度解析OpenBao 的 Priority Queue 實現基于 container/heap 的插件級優(yōu)先隊列sdk/queue 深度解析 導讀 sdk/qu后端認證鑒權密鑰管理密碼學上一篇k3s-ansible離線安裝完全手冊無網絡環(huán)境下的K3s部署下一篇探索KVKCalendar架構從CalendarType到TimelineLayout的設計原理創(chuàng)作聲明：本文部分內容由AI輔助生成（AIGC），僅供參考