Initialization: Before the first iteration of the while the only change of the max-heap is that A[i]
is increased an may therefore violate the max-heap property.
Maintenance: Immediately before the iteration i and the child that violated the max-heap prop-
erty has been exchanged thus restoring the max-heap property between these. This can only
destroy the max-heap property between i and the parent of i.
Termination: The termination condition of the while states that at the end of the iteration the
max-heap property between i and its parent is restored or the i is the root of the heap.
We see by the loop invariant that the heap property is restored at end of the iteration.
6.5 − 7
Algorithm 5 HEAP-DELETE(A, i)
Input: A max-heap A and integers i.
Output: The heap A with the element a position i deleted.
A[i] ↔A[heap-size[A]]
heap-size[A] ←heap-size[A] − 1
key ←A[i]
if key 6 A[PARENT(i)] then
MAX-HEAPIFY(A, i)
else
while i > 1 and A[PARENT(i)] < key do
A[i] ↔A[PARENT(i)]
i ←PARENT(i)
end while
end if
6.5 − 8
Given k sorted lists with a total of n elements show how to merge them in O(n lg k) time. Insert
all k elements a position 1 from each list into a heap. Use EXTRACT-MAX to obtain the first element
of the merged list. Insert element at position 2 from the list where the largest element originally
came from into the heap. Continuing in this fashion yields the desired algorithm. Clearly the
running time is O(n lg k).
6 − 2
a. A d-ary heap can be implemented using a dimensional array as follows. The root is kept in
A[1], its d children are kept in order in A[2] through A[d+1] and so on. The procedures to map a
node with index i to its parent and its jth child are given by:
D-ARY-PARENT(i)
return b(i − 2)/d + 1c
D-ARY-CHILD(i, j)
return d(i − 1) + j + 1
b. Since each node has d children the height of the tree is Θ(log
d
n).
c. The HEAP-EXTRACT-MAX algorithm given in the text works fine for d-ary heaps; the problem
is MAX-HEAPIFY. Here we need to compare the argument node to all its children. This takes
Θ(d log
d
n) and dominates the overall time spent by HEAP-EXTRACT-MAX.
9
剩余50页未读，继续阅读
zhou754506559
- 粉丝: 0
- 资源: 5
我的内容管理
展开
最新资源
- ASP.NET数据库高级操作：SQLHelper与数据源控件
- Windows98/2000驱动程序开发指南
- FreeMarker入门到精通教程
- 1800mm冷轧机板形控制性能仿真分析
- 经验模式分解：非平稳信号处理的新突破
- Spring框架3.0官方参考文档：依赖注入与核心模块解析
- 电阻器与电位器详解：类型、命名与应用
- Office技巧大揭秘：Word、Excel、PPT高效操作
- TCS3200D: 可编程色彩光频转换器解析
- 基于TCS230的精准便携式调色仪系统设计详解
- WiMAX与LTE：谁将引领移动宽带互联网?
- SAS-2.1规范草案：串行连接SCSI技术标准
- C#编程学习：手机电子书TXT版
- SQL全效操作指南：数据、控制与程序化
- 单片机复位电路设计与电源干扰处理
- CS5460A单相功率电能芯片：原理、应用与精度分析
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
