文檔教程教育【免費下載鏈接】CLRS Solutions to Introduction to Algorithms Third Edition項目地址https://gitcode.com/gh_mirrors/clr/CLRS點擊查看免費下載本篇以《算法導(dǎo)論第三版》第 6.5 節(jié)優(yōu)先隊列Priority Queues為核心基于 CLRS Solutions 倉庫的 docs/Chap06/6.5.md 習(xí)題解析系統(tǒng)講解用最大堆與最小堆實現(xiàn)優(yōu)先隊列的四大基本操作MAXIMUM / EXTRACT-MAX / INCREASE-KEY / INSERT、最小優(yōu)先隊列的對稱實現(xiàn)、正確性證明與若干工程化優(yōu)化HEAP-DELETE、k 路歸并。讀完你將掌握優(yōu)先隊列從圖示理解到偽代碼實現(xiàn)再到正確性論證的完整鏈路并能直接復(fù)現(xiàn)其中全部 9 道習(xí)題的解答與復(fù)雜度結(jié)論。一、優(yōu)先隊列堆上最實用的動態(tài)集合抽象在《算法導(dǎo)論》第 6 章Heapsort的編排中6.1–6.4 小節(jié) 依次介紹了堆的定義、MAX-HEAPIFY 維護堆性質(zhì)、BUILD-MAX-HEAP 建堆與 HEAPSORT 排序而6.5 節(jié)則是堆最經(jīng)典的應(yīng)用場景——優(yōu)先隊列Priority Queue。正如倉庫 mkdocs.yml 的導(dǎo)航配置所示該節(jié)在站點中被命名為6.5 Priority queues對應(yīng)文檔 docs/Chap06/6.5.md。優(yōu)先隊列與普通隊列的本質(zhì)區(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 $$貫穿了習(xí)題 6.5-1 與 6.5-2 的全過程演示這也是理解本節(jié)的標準實驗用例。二、優(yōu)先隊列的四大核心操作與復(fù)雜度總覽最大優(yōu)先隊列支持四類基本操作本倉庫對應(yīng)文檔結(jié)合 6.2 節(jié) 的 MAX-HEAPIFY 基礎(chǔ)可整理為操作作用復(fù)雜度依賴的子過程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 的推導(dǎo)。下面我們依次拆解 6.5 節(jié) 9 道習(xí)題。三、習(xí)題 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 移到堆頂?shù)谝淮蜗聻V由于 $13 9 1$交換 1 與 13第二次下濾由于 $12 5 1$交換 1 與 12第三次下濾由于 $6 2 1$交換 1 與 6到達葉子位置。該過程本質(zhì)上是替換堆頂 → 縮小 heap-size → MAX-HEAPIFY 下濾三步與 6.2 節(jié) MAX-HEAPIFY 的遞歸/迭代下濾完全一致單次代價為 $O(\lg n)$。四、習(xí)題 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é)點這一步的意義詳見習(xí)題 6.5-4更新新節(jié)點 key將新節(jié)點值從 $-\infty$ 提升為 10第一次上浮父節(jié)點 key 小于 10交換二者第二次上浮父節(jié)點 key 仍小于 10再次交換直到父節(jié)點不小于 10 為止。插入的代價同樣等于堆的高度即 $O(\lg n)$而HEAP-INCREASE-KEY的循環(huán)在文檔習(xí)題 6.5-5中約定為第 4–6 行這正是我們要在下一節(jié)嚴謹論證正確性的過程。五、習(xí)題 6.5-3用最小堆實現(xiàn)最小優(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$ 哨兵再調(diào)用HEAP-DECREASE-KEY。四個過程的復(fù)雜度與最大堆版本一致$O(1)$ 與 $O(\lg n)$。六、習(xí)題 6.5-4為什么插入時要先把 key 置為 $-\infty$題目MAX-HEAP-INSERT第 2 行先把新節(jié)點 key 設(shè)為 $-\infty$緊接著又要把它提升到期望值為什么要多此一舉倉庫給出的答案簡潔而關(guān)鍵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$ 哨兵是讓插入操作能夠復(fù)用HEAP-INCREASE-KEY守衛(wèi)語義的代價對稱地MIN-HEAP-INSERT則使用 $\infty$ 以通過HEAP-DECREASE-KEY的守衛(wèi)。七、習(xí)題 6.5-5用循環(huán)不變式證明 HEAP-INCREASE-KEY 的正確性題目利用如下循環(huán)不變式論證HEAP-INCREASE-KEY的正確性在while循環(huán)第 4–6 行每次迭代開始時子數(shù)組 $A[1..A.heap\text{-}size]$ 滿足最大堆性質(zhì)唯一的例外可能是$A[i]$ 大于 $A[\text{PARENT}(i)]$即唯一的一處違反。可以假設(shè)調(diào)用HEAP-INCREASE-KEY時 $A[1..A.heap\text{-}size]$ 已經(jīng)滿足最大堆性質(zhì)。倉庫給出標準的三段式證明初始化Initialization調(diào)用前 $A$ 是堆只是 $A[i]$ 可能大于其父節(jié)點因為它剛被修改為更大的值而 $A[i]$ 必然大于其子節(jié)點——否則守衛(wèi)子句會失敗、循環(huán)根本不會進入新值大于舊值舊值又大于子節(jié)點。不變式成立。保持Maintenance當我們交換 $A[i]$ 與其父節(jié)點后最大堆性質(zhì)恢復(fù)唯一的違反點轉(zhuǎn)移到了新的 $A[\text{PARENT}(i)]$它可能大于自己的父節(jié)點。把 $i$ 更新為其父節(jié)點后不變式對下一輪迭代依然成立。終止Termination循環(huán)在堆被耗盡$i 1$或 $A[i]$ 與父節(jié)點之間滿足最大堆性質(zhì)時終止。循環(huán)結(jié)束時$A$ 是一個最大堆。這個證明模式初始化 / 保持 / 終止與 6.4-2 對 HEAPSORT 的循環(huán)不變式證明 一脈相承是分析上浮式堆操作正確性的標準模板。八、習(xí)題 6.5-6借鑒 INSERTION-SORT 內(nèi)循環(huán)把三次賦值降為一次題目HEAP-INCREASE-KEY第 5 行的每次交換exchange通常需要三次賦值請借鑒INSERTION-SORT內(nèi)循環(huán)的思想把每次迭代的三次賦值減少到一次。INSERTION-SORT的內(nèi)循環(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(chǔ)[i] A[PARENT(i)]最終再一次性寫入A[i] key消除了交換所需的三次賦值中的兩次。從常數(shù)因子的角度看這是堆操作實現(xiàn)中常見的微優(yōu)化與 6.2-5 把遞歸 MAX-HEAPIFY 改為迭代 屬于同一類優(yōu)化思路。九、習(xí)題 6.5-7用優(yōu)先隊列實現(xiàn) FIFO 隊列與棧題目說明如何用優(yōu)先隊列分別實現(xiàn)先進先出隊列FIFO與棧第 10.1 節(jié)定義了這兩種數(shù)據(jù)結(jié)構(gòu)。倉庫給出的思路非常直觀棧LIFO每次插入賦予遞增的優(yōu)先級——把新元素優(yōu)先級設(shè)為 $\text{HEAP-MAXIMUM}(A) 1$。后入棧的元素優(yōu)先級最高永遠最先被EXTRACT-MAX取出隊列FIFO每次插入賦予遞減的優(yōu)先級——需要維護一個計數(shù)器每次插入時遞減。先入隊的元素優(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)先級。換言之該實現(xiàn)更多是理論可行性的演示而非工程推薦方案。十、習(xí)題 6.5-8HEAP-DELETE 的 $O(\lg n)$ 實現(xiàn)與一個典型錯誤題目HEAP-DELETE(A, i)刪除堆 $A$ 中節(jié)點 $i$ 的元素給出一個在 $n$ 元素最大堆上運行時間為 $O(\lg n)$ 的實現(xià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其正確性關(guān)鍵在于分情況討論用堆末尾元素 $A[A.heap\text{-}size]$ 替換被刪節(jié)點后若新值小于原值則可能違反父不小于子的性質(zhì)需要MAX-HEAPIFY下濾若新值大于原值則可能違反子不大于父的性質(zhì)需要HEAP-INCREASE-KEY上浮。兩種修復(fù)路徑都是 $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$。刪除前堆結(jié)構(gòu)為15 / \ 7 9 / \ / \ 1 2 3 8錯誤算法用末尾元素 8 覆蓋 2 并下濾后得到15 / \ 7 9 / \ / 1 8 3此時 $8 7$違反了最大堆性質(zhì)右子樹根 7 比其左孩子 8 更小。原因正是沒有考慮新值大于原值時應(yīng)上浮這一分支——可見對稱地處理上浮/下濾是這類刪除實現(xiàn)的關(guān)鍵。十一、習(xí)題 6.5-9用最小堆做 k 路歸并$O(n\lg k)$ 排序合并題目給出一個 $O(n\lg k)$ 時間的算法將 $k$ 個有序列表合并為一個有序列表其中 $n$ 是所有輸入列表的元素總數(shù)提示用最小堆做 k 路歸并。這是優(yōu)先隊列最著名的應(yīng)用之一——k 路歸并k-way merge。倉庫給出的算法描述為從每個列表中取出一個元素放入最小堆同時記錄該元素來自哪個列表每次從堆中取出最小元素并從它所屬的列表中補入下一個元素除非該列表已空重復(fù)直至堆為空?？偣灿?$n$ 步每一步對大小為 $k$ 的堆做一次插入或提取代價為 $\lg k$因此總復(fù)雜度為 $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該過程復(fù)用了本文第五節(jié)實現(xiàn)的HEAP-EXTRACT-MIN與MIN-HEAP-INSERT是優(yōu)先隊列從抽象數(shù)據(jù)結(jié)構(gòu)走向真實排序算法的經(jīng)典落點。十二、倉庫中的配套資料與延伸閱讀本節(jié)內(nèi)容在 CLRS Solutions 倉庫中的完整落點為 docs/Chap06/6.5.md其直接前置章節(jié)包括6.1 Heaps堆的定義、高度 $\lfloor\lg n\rfloor$、葉子下標 $\lfloor n/2\rfloor 1 \sim n$ 等基礎(chǔ)性質(zhì)6.2 Maintaining the heap propertyMAX-HEAPIFY / MIN-HEAPIFY 及迭代式實現(xiàn)6.5-1 的下濾步驟直接依賴它6.3 Building a heap 與 6.4 The heapsort algorithm建堆與排序構(gòu)成優(yōu)先隊列操作的完整前置知識章節(jié)問題 6-2d 叉堆把二元堆推廣為 d 元堆EXTRACT-MAX / INSERT / INCREASE-KEY 的復(fù)雜度變?yōu)?$O(d\log_d n)$ 與 $O(\log_d n)$可作為本節(jié)操作復(fù)雜度的進階練習(xí)章節(jié)問題 6-3Young 矩陣利用類似 MAX-HEAPIFY 的下濾思想在 $m\times n$ 矩陣上實現(xiàn) $O(mn)$ 的 EXTRACT-MIN / 插入 / 排序。整個倉庫以 Markdown KaTeX 編寫由 MkDocs 與 Material for MkDocs 構(gòu)建為靜態(tài)站點見 README.md 與 mkdocs.yml 中的 KaTeX 與主題配置所有數(shù)學(xué)公式均以標準 LaTeX 語法渲染便于在移動端與桌面端閱讀。贊分享文檔教程教育【免費下載鏈接】CLRS Solutions to Introduction to Algorithms Third Edition項目地址https://gitcode.com/gh_mirrors/clr/CLRS點擊查看免費下載相關(guān)推薦Swift Algorithm Club 優(yōu)先隊列Priority Queue完全指南基于堆的 Swift 實現(xiàn)與實戰(zhàn)Swift Algorithm Club 優(yōu)先隊列Priority Queue完全指南基于堆的 Swift 實現(xiàn)與實戰(zhàn) 優(yōu)先級隊列Priority Qu示例工程教程最大堆上的優(yōu)先隊列全解CLRS 第 6.5 節(jié)習(xí)題精講與 C 實現(xiàn)剖析最大堆上的優(yōu)先隊列全解CLRS 第 6.5 節(jié)習(xí)題精講與 C 實現(xiàn)剖析 本文以《算法導(dǎo)論》Introduction to Algorithms第 6.文檔教程示例工程OpenBao 的 Priority Queue 實現(xiàn)基于 container/heap 的插件級優(yōu)先隊列sdk/queue 深度解析OpenBao 的 Priority Queue 實現(xiàn)基于 container/heap 的插件級優(yōu)先隊列sdk/queue 深度解析 導(dǎo)讀 sdk/qu后端認證鑒權(quán)密鑰管理密碼學(xué)上一篇k3s-ansible離線安裝完全手冊無網(wǎng)絡(luò)環(huán)境下的K3s部署下一篇探索KVKCalendar架構(gòu)從CalendarType到TimelineLayout的設(shè)計原理創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考