算法导论第2版：43以内插入排序优化与习题1.2-2解答

需积分: 10 18 浏览量更新于2024-07-20 收藏 266KB PDF 举报

《算法导论》第二版习题解答是一份针对Thomas H. Cormen、Charles E. Leiserson 和 Ronald L. Rivest 著名教材《算法导论》中的练习题提供的解答指南。作者Philip Bille并非官方作者，他强调本文档仅供个人参考，不承担任何责任，并提醒读者在尝试解答前应独立思考，尽量自己解决问题，仅在遇到困难或怀疑自己的解答时才可查阅。这份文档并非最终版本，更新频率较低，最后更新日期为2002年12月9日。其中一节内容涉及比较两种排序算法——插入排序（Insertion Sort）和归并排序（Merge Sort）。题目指出，在输入规模满足8n^2 < 64nlg(n)，即当n小于8lg(n)大约等于13.4时，插入排序的效率优于归并排序。这个结论适用于n在2到43之间的整数，这个发现是通过计算得出的。为了优化性能，作者建议对于输入大小小于等于43的情况，可以改用插入排序，以改进运行时间。另一个例子展示了在假设所有月份有30天且所有年份有365天的前提下，可能涉及到的时间管理问题，但具体题目未给出，可能是关于日期处理或者算法应用的一个场景。需要注意的是，这份文档旨在辅助学习，而非替代深入理解和实践，因此在阅读过程中，不仅要理解答案，更要关注解题思路和背后的算法原理。同时，由于可能存在错误，使用时需谨慎验证和理解。

Initialization: Before the ﬁrst 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 ﬁrst 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

n).

c. The HEAP-EXTRACT-MAX algorithm given in the text works ﬁne 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

n) and dominates the overall time spent by HEAP-EXTRACT-MAX.

剩余50页未读，继续阅读

williamsjohnson

粉丝: 0
资源: 6

算法导论第2版：43以内插入排序优化与习题1.2-2解答

算法导论第2版 习题解答

算法导论中文第三版习题答案

算法导论第2版习题解答与解析

算法导论第二版习题解答（英文）

算法导论二英文版习题解答

算法导论第四章习题解答

算法导论第二版习题解答

算法导论第三版习题解答

算法导论第二版习题解答参考

算法导论第二版习题解答精要

最新资源

算法导论第2版习题解答