《算法导论》第六章-优先级队列（伪代码）

蔚落 2022-08-13 07:58 156阅读 0赞

优先级队列

伪代码：

//返回优先级队列的最大值

Heap\_Max(A)

return A\[1\]

end

运行时间为Θ(1)

//去掉并返回优先级队列中的最大值

/\*  
\* 先记录最大值，将数组最后的元素与第一个元素交换，数组大小减一，  
\* 调用max\_heapify函数保证最大堆的性质，最后返回最大值。  
\*/

Heap\_Extract\_Max(A, length)

if length < 1 then error "heap under flow"

max = A\[1\]

A\[1\] = A\[length\]

length --

Max\_Heapify(A, 1, length)

return max

end

运行时间为Θ(lgn)

//将优先级队列中的i元素的值增加到key（key >= A\[i\]）

Heap\_Increase\_Key(A, i, key)  
if key < A\[i\] then error  
A\[i\] = key  
while i>1 && A\[PARENT(i)\] <A\[i\]  
do exchange A\[i\] <-> A\[PARENT(i)\]  
i = PARENT(i)

end

运行时间为Θ(lgn)

//将元素插入优先级队列.

向最大堆中插入新的关键字。新的关键字插入在优先级的队尾部，然后从尾部的父节点开始自底向上调整堆

MAX\_HEAP\_INSERT(A,key)  
heap\_size\[A\] = heap\_size\[A\]+1  
A\[heap\_size\[A\]\] = -0; //把队尾赋值0或无穷小  
HEAP\_INCREASE\_KEY(A,heap\_size\[A\],key)

end

运行时间为Θ(lgn)

[详细资料参考：http://www.cnblogs.com/Anker/archive/2013/01/23/2873951.html][http_www.cnblogs.com_Anker_archive_2013_01_23_2873951.html]

[http_www.cnblogs.com_Anker_archive_2013_01_23_2873951.html]: http://www.cnblogs.com/Anker/archive/2013/01/23/2873951.html

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关算法导论学习笔记第六章堆排序

实际中，待排序的数很少是单独的数值，它们通常是称为记录的数据集的一部分，每个记录包含一个关键字，即排序问题中要重排的值，记录的剩余部分由卫星数据组成，通常是要与关键字一同存取的

约定不等于承诺〃/ 2022年11月18日 08:05/ 0 赞/ 203 阅读

相关《算法导论》第七章-快速排序（伪代码）

快速排序伪代码： QuickSort(A,p,r) if p<r q = Partition(A,p,r) //确定划分位置 QuickSort(A,p,q

旧城等待，/ 2022年08月13日 08:28/ 0 赞/ 295 阅读

相关《算法导论》第六章-优先级队列（伪代码）

优先级队列伪代码： //返回优先级队列的最大值 Heap\_Max(A) return A\[1\] end 运行时间为Θ(1) //去

蔚落/ 2022年08月13日 07:58/ 0 赞/ 157 阅读

相关《算法导论》第六章-堆排序（伪代码）

堆排序根据《算法导论》中的伪代码，改写如下，可能更好理解伪代码： //建堆,运行时间的界T(n) =O(N) BuildHeap(A) n = len

蔚落/ 2022年08月13日 07:00/ 0 赞/ 380 阅读

相关算法导论第三章函数的增长

渐近记号（1）渐近上界记号O（大写O）含义：渐近地给出了一个函数在常量因子内的上界： O(g(n))=\{f(n):存在正常量c和n0，使得对所有n>=n0

小咪咪/ 2022年07月16日 00:16/ 0 赞/ 182 阅读

相关第1章导论

这系列博客主要记录自己学习《算法：c语言实现》的过程。学习方法有二： 1、Robert Sedgewick普林斯顿大学公开课，[课程链接见B站，带有中文字幕高大上][

缺乏、安全感/ 2022年06月07日 11:23/ 0 赞/ 254 阅读

相关算法导论-第六部分-读书笔记

第二十一章用于不相交集合的数据结构 > 第二十一章本来是第五部分里的，但它的内容和第六部分关系更为密切，所以放到了这里。 21.1 不相交集合的操作不相交集合

约定不等于承诺〃/ 2022年05月31日 13:15/ 0 赞/ 339 阅读

相关算法导论第6章堆排序答案

一、概念 1.堆的定义与性质（1）堆是一种数组对象（2）堆可以被视频一棵完全二叉树，二叉树的层次遍历结果与数组元素的顺序对应，树根为A\[1\]。对于数组中第

╰+哭是因爲堅強的太久メ/ 2022年05月15日 11:40/ 0 赞/ 220 阅读

相关算法导论第7章快速排序答案

一、概念快速排序是基于分治模式的，选择一个数作为主元，经过一遍扫描，所有小于主元的数放在主元的左边，大于主元的数放在主元的右边，这样就划分成了两组数据。然后对两组数分别

﹏ヽ暗。殇╰゛Y/ 2022年05月14日 00:45/ 0 赞/ 275 阅读

相关 Android-算法-优先级队列

class PriorityQueue { private long[] a = null; private int nItems = 0; p

ゝ一世哀愁。/ 2022年04月05日 10:22/ 0 赞/ 271 阅读