首页 / 算法 / 算法导论——lec 06 堆排序
算法导论——lec 06 堆排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法导论——lec 06 堆排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3015字，纯文字阅读大概需要5分钟。
内容图文
堆数据结构是一种数组对象，它可以被视为一颗完全二叉树，树中每个节点和数组中存放该节点值的那个元 素对应。如果表示堆的数组为A，那么树的根为A[1]。
一、 堆
1. 表示堆的数组A是一个具有两个属性的对象：length(A)是数组中的元素个数，heap-size(A)是存放在A中的堆的
元素个数；A[heap-size(A)]之后的元素都不属于相应的堆。也就是：Heap-size(A)<=length(A)。
2. 给定某个节点的下标i，其父节点PARENT(i)，左儿子LEFT(i)和右儿子RIGHT(i)可以表示为
PARENT(i): floor(i/2)
LEFT(i): 2i
RIGHT(i): 2i +１
3.两种堆：最大堆——除了根节点以外，每个结点都满足：A[PARENT(i)] ≥A[i]
最小堆——除了根节点以外，每个结点都满足：A[PARENT(i)] ≤A[i]
4. 堆可以被看成一棵树，节点在堆中的高度定义为从本节点到叶子的最长简单下降路径上边的个 数。堆的高度定义为树根的高度，为Θ(lgn)。
二、 Max-Heapify
1. MAX-HEAPIFY是对最大堆进行操作的重要的子程序，调整A[i]在堆中的位置：
Max-Heapify(A, i) 1 l <-- Left(i) 2 r <-- Right(i) 3 if l <= heap-size(A) and A[l] >= A[i] 4 then largest <-- l 5 else largest <-- i 6 if r <= heap-size(A) and A[r] >= A[largest] 7 then largest <--r 8 if largest != i 9 then exchange A[i] <--> A[largest] 10 <span style="white-space:pre"> </span>Max-Heapify(A, largest)
2. 当MAX-HEAPIFY作用在一棵以节点i为根的， 大小为n的子树上时，其运行时间为调整元素A[i]，A[LEFT(i)]
和A[RIGHT(i)]的关系时所用时间Θ(1)，再加上对以i的某个子结点为根的子树递归调用MAX-HEA PIFY所需的
时间。i结点的子树大小至多为2n/3，那么MAX-HEAPFY的运行时间为：
T(n) ≤T(2n/3) + Θ(1)
根据主定理，该递归式的解为T(n) ≤Θ(lgn)
三、 建堆
1. 我们可以自底向上的用MAX-HEAPIFY来将一个数组A[1..n]变成一个最大堆。过程BUILD-MAX- HEAP对树中的
每一个其他节点都调用一次MAX-HEAPIFY。
Build-Max-Heap(A) 1 heap-size[A] = length[A] 2 for i <-- floor(length[A]/2) downto 1 3 do Max-Heapify(A, i)2. 循环不变式证明正确性：在第2~3行中for循环的每一次迭代开始时，节点i+1，i+2，…n都是一个最大堆的根。
3. 我们可以这样来计算BUILD-MAX-HEAP运行时间的一个简单上界：每次调用MAX-HEAPFY的时间为O(lgn)，共有O(n)次调用，故运行时间为O(nlgn)。这个界尽管是对的，但是从渐近意义上讲不够紧确。
4. BUILD-MAX-HEAP精确上界：
MAX-HEAPIFY作用在高度为h的结点上的时间为O(h)，我们可以将BUILD-MAX-HEAP的代价表达为上确界
由于
于是，BUILD-MAX-HEAP的运行时间的界为O(n)
四、 堆排序算法
1. 开始时，堆排序算法先后用BUILD-MAX-HEAP 将输入数组A[1..n]构造成一个最大堆，因为数组中最大元素在
A[1]，可以通过把它与A[n]互换来达到最终正确的位置。接下来，如果从堆中去掉结点n，可以很容易地将
A[1..n-1]建成最大堆。原来根的子女仍是最大堆，而新的根元素可能违背了最大堆性质。
这 时调用MAX-HEAPIFY(A,1)就可以保持这一性质，在A[1..(n-1)]中构建出最大堆。
Heap-Sort(A) 1 Build-Max-Heap(A) 2 for i <-- length[A] down to 2 3 do exchange A[1] <--> A[i] 4 heap-size[A] <-- heap-size[A]-1 5 Max-Heapify(A, 1)HEAPSORT过程的时间代价为O(nlgn)，其中调用BUILD-MAX-HEAP的时间为O(n)，n次MAX-HEAPIFY调用中每一次的时间代价为O(lgn)。
2. 优先级队列：
作业调度程序：找出优先级最高的作业、插入作业、调整作业优先级
优先级队列是一种用来维护由一组元素构成的集合S的数据结构，这一组元素中的每一个都有一个关键字key，
一个最大优先级队列支持以下操作：
a、 INSERT(S,x)：把元素x插入集合S；
Max-Heap-Insert(A, key) 1 heap-size[A] <-- heap-size[A] + 1 2 A[heap-size[A]] <-- -INF 3 Heap-Increase-Key(A, heap-size[A], key)
b、 MAXIMUM(S)：返回S中具有最大关键字的元素；时间复杂度为Θ(1)
Heap-Maxium(A) 1 return A[1]
c、 EXTRACT-MAX(S)：去掉并返回S中的具有最大关键字的元素；时间复杂度为O(log n)
Heap-Extract-Max(A) 1 if heap-size(A) < 1 2 then error "heap underflow" 3 max <-- A[1] 4 A[1] <-- A[heap-size[A]) 5 heap-size(A) <-- heap-size(A)-1 6 Max-Heapify(A, 1) 7 return max
d、 INCREASE-KEY(S,x,k)：将元素x的关键字的值增加到k，这里k值不能小于x的原关键字的值。
Heap-Increase-Key(A, i, key) 1 if key < A[i] 2 then error "new key is smaller than the current key" 3 A[i] <-- key 4 while i > 1 and A[Parent(i)] < A[i] 5 do exchange A[i] <--> A[Parent(i)] 6 i <-- Parent[i]
原文：http://blog.csdn.net/uilotus/article/details/37322157
内容总结
以上是互联网集市为您收集整理的算法导论——lec 06 堆排序全部内容，希望文章能够帮你解决算法导论——lec 06 堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。