算法导论 第6章

6.5-3

 1 HEAP-MINIMUM(A)
 2   return A[1]
 3 
 4 HEAP-EXTRACT-MIN(A)
 5   if A.heap-size < 1
 6       error "heap underflow"
 7   min = A[1]
 8   A[1] = A[A.heap-size]
 9   A.heap-size = A.heap-size - 1
10   MIN-HEAPIFY(A, 1)
11   return min
12 
13 HEAP-DECREASE-KEY(A, i, key)
14     if key > A[i]
15         error "new key is biger than current key"
16     A[i] = key
17     while i < A.heap-size and A[PARENT(i)] > A[i]
18         exchange A[i] and A[PARENT(i)]
19         i = PARENT(i)
20 
21 MIN-HEAP-INSERT(A, key)
22 A.heap-size = A.heap-size + 1
23 A[A.heap-size] = INT_MAX
24 HEAP-DECREASE-KEY(A, A.heap-size, key)

6.5-6

解答:在题目中通过交换变量A[i]与A[PARENT(i)]实现;通过借鉴插入排序的做法,令A[i] = A[PARENT(i)],直到A[PARENT(i)] > A[i], 然后再位置i上插入关键字。

6.5-7

队列的实现:以入队的时间作为关键字建立最小优先队列

栈的实现:以入队的时间作为关键字建立最大优先队列

6.5-8

假设为最大堆,在删除关键字A[i]后,由于要保持堆的结构性,选择A[A.heap-size]替代A[i];

1、若替代后,A[i] < A[PARENT(i)], 使用MAX-HEAPIFY(A, i)

2、若替代后,A[i] > A[PARENT(i)], 使用上滤技术

 1 Input: A max-heap and an integers i
 2 Output: The heap A with element a position i delete
 3 
 4 A[i] = A[A.heap-size]
 5 A.heap-size = A.heap-size - 1
 6 key = A[i]
 7 if key <= A[PARENT(i)]
 8     MAX-HEAPIFY(A, i)
 9 else
10     while i > 1 and A.[PARENT(i)] < key
11         A[i] = A[PARENT(i)]
12         i = PARENT(i)
13     A[i] = key

6.5-9

解答:

1、选择k个链表的第一个元素入最小堆

2、将堆中的最小元素放入排序的表中,再在最小元素所在的链表中选择下一个元素加入最小堆中

3、重复如此,直到排序完成

原文地址:https://www.cnblogs.com/tallisHe/p/4064143.html