文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本篇以《算法导论第三版》第 6.5 节优先队列Priority Queues为核心基于 CLRS Solutions 仓库的 docs/Chap06/6.5.md 习题解析系统讲解用最大堆与最小堆实现优先队列的四大基本操作MAXIMUM / EXTRACT-MAX / INCREASE-KEY / INSERT、最小优先队列的对称实现、正确性证明与若干工程化优化HEAP-DELETE、k 路归并。读完你将掌握优先队列从图示理解到伪代码实现再到正确性论证的完整链路并能直接复现其中全部 9 道习题的解答与复杂度结论。一、优先队列堆上最实用的动态集合抽象在《算法导论》第 6 章Heapsort的编排中6.1–6.4 小节 依次介绍了堆的定义、MAX-HEAPIFY 维护堆性质、BUILD-MAX-HEAP 建堆与 HEAPSORT 排序而6.5 节则是堆最经典的应用场景——优先队列Priority Queue。正如仓库 mkdocs.yml 的导航配置所示该节在站点中被命名为6.5 Priority queues对应文档 docs/Chap06/6.5.md。优先队列与普通队列的本质区别在于出队顺序不取决于入队先后而取决于元素的优先级。当优先级就是元素本身的值时一个最大堆天然就是一个最大优先队列——堆顶A[1]恒为全局最大元素。CLRS 仓库用一组目标堆$$ A \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \rangle $$贯穿了习题 6.5-1 与 6.5-2 的全过程演示这也是理解本节的标准实验用例。二、优先队列的四大核心操作与复杂度总览最大优先队列支持四类基本操作本仓库对应文档结合 6.2 节 的 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 节 9 道习题。三、习题 6.5-1HEAP-EXTRACT-MAX 的完整运行过程题目在堆 $A \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \rangle$ 上演示HEAP-EXTRACT-MAX的逐步操作。原始堆形态如下仓库给出的五步推演配图为 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 节 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$追加哨兵节点heap-size加一在末尾追加一个值为 $-\infty$ 的节点这一步的意义详见习题 6.5-4更新新节点 key将新节点值从 $-\infty$ 提升为 10第一次上浮父节点 key 小于 10交换二者第二次上浮父节点 key 仍小于 10再次交换直到父节点不小于 10 为止。插入的代价同样等于堆的高度即 $O(\lg n)$而HEAP-INCREASE-KEY的循环在文档习题 6.5-5中约定为第 4–6 行这正是我们要在下一节严谨论证正确性的过程。五、习题 6.5-3用最小堆实现最小优先队列题目为最小优先队列写出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)与最大优先队列逐一对齐即可得到HEAP-MINIMUM返回最小值HEAP-EXTRACT-MIN取出最小值后以堆末尾元素填补并用MIN-HEAPIFY下滤HEAP-DECREASE-KEY把 key 减小后自底向上与父节点比较并上浮MIN-HEAP-INSERT先追加一个 $\infty$ 哨兵再调用HEAP-DECREASE-KEY。四个过程的复杂度与最大堆版本一致$O(1)$ 与 $O(\lg n)$。六、习题 6.5-4为什么插入时要先把 key 置为 $-\infty$题目MAX-HEAP-INSERT第 2 行先把新节点 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)开头有一条守卫guard子句if key A[i] error new key is smaller than current key而MAX-HEAP-INSERT中新增节点的当前位置A[A.heap-size]尚未被赋值或是旧值如果不先用 $-\infty$ 初始化就无法保证新 key 不小于当前值从而无法通过守卫。换句话说$-\infty$ 哨兵是让插入操作能够复用HEAP-INCREASE-KEY守卫语义的代价对称地MIN-HEAP-INSERT则使用 $\infty$ 以通过HEAP-DECREASE-KEY的守卫。七、习题 6.5-5用循环不变式证明 HEAP-INCREASE-KEY 的正确性题目利用如下循环不变式论证HEAP-INCREASE-KEY的正确性在while循环第 4–6 行每次迭代开始时子数组 $A[1..A.heap\text{-}size]$ 满足最大堆性质唯一的例外可能是$A[i]$ 大于 $A[\text{PARENT}(i)]$即唯一的一处违反。可以假设调用HEAP-INCREASE-KEY时 $A[1..A.heap\text{-}size]$ 已经满足最大堆性质。仓库给出标准的三段式证明初始化Initialization调用前 $A$ 是堆只是 $A[i]$ 可能大于其父节点因为它刚被修改为更大的值而 $A[i]$ 必然大于其子节点——否则守卫子句会失败、循环根本不会进入新值大于旧值旧值又大于子节点。不变式成立。保持Maintenance当我们交换 $A[i]$ 与其父节点后最大堆性质恢复唯一的违反点转移到了新的 $A[\text{PARENT}(i)]$它可能大于自己的父节点。把 $i$ 更新为其父节点后不变式对下一轮迭代依然成立。终止Termination循环在堆被耗尽$i 1$或 $A[i]$ 与父节点之间满足最大堆性质时终止。循环结束时$A$ 是一个最大堆。这个证明模式初始化 / 保持 / 终止与 6.4-2 对 HEAPSORT 的循环不变式证明 一脉相承是分析上浮式堆操作正确性的标准模板。八、习题 6.5-6借鉴 INSERTION-SORT 内循环把三次赋值降为一次题目HEAP-INCREASE-KEY第 5 行的每次交换exchange通常需要三次赋值请借鉴INSERTION-SORT内循环的思想把每次迭代的三次赋值减少到一次。INSERTION-SORT的内循环并不真正交换而是不断把较大的元素向后搬移、最后一次性落位。把这一思想移植到堆的上浮过程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这样每轮迭代只执行一次赋值A[i] A[PARENT(i)]最终再一次性写入A[i] key消除了交换所需的三次赋值中的两次。从常数因子的角度看这是堆操作实现中常见的微优化与 6.2-5 把递归 MAX-HEAPIFY 改为迭代 属于同一类优化思路。九、习题 6.5-7用优先队列实现 FIFO 队列与栈题目说明如何用优先队列分别实现先进先出队列FIFO与栈第 10.1 节定义了这两种数据结构。仓库给出的思路非常直观栈LIFO每次插入赋予递增的优先级——把新元素优先级设为 $\text{HEAP-MAXIMUM}(A) 1$。后入栈的元素优先级最高永远最先被EXTRACT-MAX取出队列FIFO每次插入赋予递减的优先级——需要维护一个计数器每次插入时递减。先入队的元素优先级最高因此最先出队。仓库同时指出了两个重要缺陷Both are not very efficient. Furthermore, if the priority can overflow or underflow, so will eventually need to reassign priorities.其一这种做法并不高效每次都依赖堆操作与全局最大/最小值的维护其二若优先级可溢出或下溢则最终需要重新分配reassign全部优先级。换言之该实现更多是理论可行性的演示而非工程推荐方案。十、习题 6.5-8HEAP-DELETE 的 $O(\lg n)$ 实现与一个典型错误题目HEAP-DELETE(A, i)删除堆 $A$ 中节点 $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]$ 替换被删节点后若新值小于原值则可能违反父不小于子的性质需要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 路归并。这是优先队列最著名的应用之一——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该过程复用了本文第五节实现的HEAP-EXTRACT-MIN与MIN-HEAP-INSERT是优先队列从抽象数据结构走向真实排序算法的经典落点。十二、仓库中的配套资料与延伸阅读本节内容在 CLRS Solutions 仓库中的完整落点为 docs/Chap06/6.5.md其直接前置章节包括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建堆与排序构成优先队列操作的完整前置知识章节问题 6-2d 叉堆把二元堆推广为 d 元堆EXTRACT-MAX / INSERT / INCREASE-KEY 的复杂度变为 $O(d\log_d n)$ 与 $O(\log_d n)$可作为本节操作复杂度的进阶练习章节问题 6-3Young 矩阵利用类似 MAX-HEAPIFY 的下滤思想在 $m\times n$ 矩阵上实现 $O(mn)$ 的 EXTRACT-MIN / 插入 / 排序。整个仓库以 Markdown KaTeX 编写由 MkDocs 与 Material for MkDocs 构建为静态站点见 README.md 与 mkdocs.yml 中的 KaTeX 与主题配置所有数学公式均以标准 LaTeX 语法渲染便于在移动端与桌面端阅读。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐Swift Algorithm Club 优先队列Priority Queue完全指南基于堆的 Swift 实现与实战Swift Algorithm Club 优先队列Priority Queue完全指南基于堆的 Swift 实现与实战 优先级队列Priority Qu示例工程教程最大堆上的优先队列全解CLRS 第 6.5 节习题精讲与 C 实现剖析最大堆上的优先队列全解CLRS 第 6.5 节习题精讲与 C 实现剖析 本文以《算法导论》Introduction to Algorithms第 6.文档教程示例工程OpenBao 的 Priority Queue 实现基于 container/heap 的插件级优先队列sdk/queue 深度解析OpenBao 的 Priority Queue 实现基于 container/heap 的插件级优先队列sdk/queue 深度解析 导读 sdk/qu后端认证鉴权密钥管理密码学上一篇k3s-ansible离线安装完全手册无网络环境下的K3s部署下一篇探索KVKCalendar架构从CalendarType到TimelineLayout的设计原理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考