『算法导论』第 6 章

主要内容

本章介绍堆排序(heapsort)算法。

堆排序算法的复杂度和归并排序相同,但是仅需要常数个额外的元素空间存储临时数据。堆(heap)不仅仅用在堆排序中,还可以构造一种有效的优先队列(priority queue)。

二叉堆一般用数组实现,可以看成是一个近似的完全二叉树,树的每个节点对应数组中的一个元素。根节点为$A[1]$,给定一个下标$i$,很容易计算它的父节点、左孩子和右孩子的下标分别为$\lfloor i/2 \rfloor$,$2i$,$2i+1$。需注意,用C语言实现时,数组要多分配一个元素的空间。

1
2
3
4
5
6
7
8
9
typedef struct __heap {
int length; // 容纳元素个数的上限
int heap_size; // 当前元素个数
int *data; // 存放元素的内存
} Heap;

#define PARENT(i) (i/2)
#define LEFT(i) (2*i)
#define RIGHT(i) (2*i+1)

二叉堆可分为两种:最大堆和最小堆。在最大堆中,最大堆性质指的除了根以外,其它所有节点都要满足父节点的值大于或等于当前节点的值。最小堆性质相反。堆排序算法中使用的是最大堆。

由于堆可看作一颗完全二叉树,所以包含$n$个元素的堆的高度为$\Theta(\lg n)$。堆结构上的一些基本操作至多与树的高度成正比,即时间复杂度为$O(\lg n)$。

维护堆的性质

下面的MaxHeapify过程维护以root为根节点的堆的最大堆性质。在调用它的时候,假定根节点root的两个孩子都是最大堆,通过让新进的元素在最大堆中“逐级下降”,使得子树重新遵循最大堆的性质。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void MaxHeapify(Heap *hp, int root)
{
int left = LEFT(root);
int right = RIGHT(root);
int largest;

// 在root, left和right中选出值最大的,记录在largest中
if (left <= hp->heap_size && hp->data[left] > hp->data[root]) {
largest = left;
} else {
largest = root;
}
if (right <= hp->heap_size && hp->data[right] > hp->data[largest]) {
largest = right;
}

// 如果root是最大的,则满足最大堆性质,函数结束
// 否则
if (largest != root) {
Exch(hp->data, root, largest); // 将最大值交换到根部
MaxHeapify(hp, largest); // 以该节点为根的树可能不满足性质,递归调用
}
}

由于每个子树的大小至多为$2n/3$(最坏情况发生在最底层恰好半满的时候),所以上述过程的递归式为:

$$
T(n) \le T(2n/3) + \Theta(1)
$$

根据主定理,递归式的解为$T(n) = O(\lg n)$,对于树高为$h$的节点,MaxHeapify的时间复杂度为$O(h)$。

建堆

可以用自底向上的方法利用过程MaxHeapify把数组转换为最大堆。叶节点的下标范围是从$\lfloor n/2 \rfloor+1$到$n$,每个叶节点可以看成只包含一个元素的堆。BuildMaxHeap堆树中的其它节点都调用一次MaxHeapify

1
2
3
4
5
6
7
8
9
10
11
// 需注意数组A[]要从下标1开始存放数据,n为数组的实际大小减1
void BuildMaxHeap(Heap *hp, int A[], int n)
{
hp->length = n;
hp->heap_size = n;
hp->data = A;

for (int i = hp->heap_size/2; i >= 1; i--) {
MaxHeapify(hp, i);
}
}

BuildMaxHeap需要调用$O(n)$次MaxHeapify,所以,总的时间复杂度为$O(n \lg n)$,但这并不是渐近紧确界。实际上,可以计算得到它的时间复杂度为$O(n)$,可以在线性时间内将一个无序数组构造成一个最大堆。

堆排序算法

堆排序算法的实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
// 数组A[]要从下标1开始存放数据,n为数组的实际大小减1
void HeapSort(int A[], int n)
{
Heap heap;
BuildMaxHeap(&heap, A, n); // 构建最大堆

for (int i = n; i >= 2; i--) {
Exch(heap.data, 1, i); // 将最大值A[1]与A[n]交换,于是A[1]放到正确的位置
heap.heap_size--; // 将节点n从堆中去掉
MaxHeapify(&heap, 1); // 新的根节点可能违背最大堆的性质,重新维护
}
}

每次调用BuildMaxHeap的时间复杂度为$O(n)$,调用了$n-1$次MaxHeapify,每次时间为$O(\lg n)$。所以堆排序算法的时间复杂度为$O(n \lg n)$。下面的测试代码展示了使用方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 打印堆的内容
void PrintHeap(Heap *hp)
{
for (int i = 1; i <= hp->heap_size; i++) {
printf("%d ", hp->data[i]);
}
printf("\n");
}

void TestHeapSort()
{
Heap heap;
int A[11] = {-1, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
HeapSort(A, 10);
}

优先队列

堆的另一个常见应用是优先队列。类似地,优先队列也有两种形式,最大优先队列和最小优先队列。本章基于最大堆实现最大优先队列。优先队列应用广泛,比如用于操作系统的作业调度。一个最大有限队列有如下基本操作:

  • INSERT(S, x):把元素插入到集合中
  • MAXIMUM(S):返回集合中具有最大关键字的元素
  • EXTRACT-MAX(S):去掉并返回集合中具有最大关键字的元素
  • INCREASE-KEY(S, x, k):将元素的关键字增加

显然,优先队列可以用堆来实现。过程HeapMaximum可以在$O(1)$时间内完成:

1
2
3
4
int HeapMaximum(Heap *hp)
{
return hp->data[1];
}

过程HeapExtractMax实现EXTRACT-MAX操作,代码如下:

1
2
3
4
5
6
7
8
9
10
11
int HeapExtractMax(Heap *hp)
{
assert(hp->heap_size >= 1);

int max = hp->data[1];
hp->data[1] = hp->data[hp->heap_size];
hp->heap_size--;
MaxHeapify(hp, 1);

return max;
}

它的时间复杂度为$O(\lg n)$,因为除了时间复杂度为$O(\lg n)$的MaxHeapify以外,其它操作都在常数时间内完成。

过程HeapIncreaseKey能够实现INCREASE-KEY功能,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void HeapIncreaseKey(Heap *hp, int idx, int key)
{
if (key < hp->data[idx]) {
printf("Key is smaller than current!\n");
return;
}

hp->data[idx] = key;
// 重新维护最大堆性质
while (idx > 1 && hp->data[PARENT(idx)] < hp->data[idx]) {
Exch(hp->data, idx, PARENT(idx));
idx = PARENT(idx);
}
}

HeapIncreaseKey的时间复杂度为$O(\lg n)$,因为在算法中,从关键字更新的节点到根节点的路径长度为$O(\lg n)$。

过程MaxHeapInsert能够实现INSERT操作,代码如下:

1
2
3
4
5
6
void MaxHeapInsert(Heap *hp, int key)
{
hp->heap_size++;
hp->data[hp->heap_size] = INT_MIN;
HeapIncreaseKey(hp, hp->heap_size, key);
}

在包含$n$个元素的堆上,MaxHeapInsert的运行时间为$O(\lg n)$。

综上所述,在一个包含$n$个元素的堆中,所有优先队列的操作都可以在$O(\lg n)$时间内完成。

下面的测试代码展示了使用方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
void TestPriorityQueue(void)
{
Heap heap;
int A[20] = {-1, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
BuildMaxHeap(&heap, A, 10);
PrintHeap(&heap);
HeapMaximum(&heap);
PrintHeap(&heap);
HeapIncreaseKey(&heap, 2, 22);
PrintHeap(&heap);
MaxHeapInsert(&heap, 25);
PrintHeap(&heap);
}

习题解答

练习题

6.1-1 解答:高度为$h$的堆中,元素最多有$2^{h+1}$个,最少有$2^h+1$个。

6.1-2 解答:根据上面的结果,高度为$h$的堆,元素个数$n$范围是$[2^h+1, 2^{h+1}-1]$,所以$h = \lfloor \lg n \rfloor$。

6.1-3 解答:根据最大堆性质,很容易得证。

6.1-4 解答:最小元素位于数组最后。

6.1-5 解答:已排序好的数组是最小堆。

6.1-6 解答:不是。

6.1-7 解答:叶子节点没有孩子节点,即有$2i > n$,即$i > \lfloor n/2 \rfloor$,得证。

6.2-1 解答:略。

6.2-2 解答:略。

6.2-3 解答:则此时满足最大堆性质,数组不会有任何修改。

6.2-4 解答:当$i > A.heapsize/2$时,节点为叶节点,调用函数,largest即为i,不会修改数组。

6.2-5 解答:MAX-HEAPIFY用递归实现,可能产生低效代码,可以用循环结构替代递归。待完成。

6.2-6 解答:待完成。

6.3-1 解答:略。

6.3-2 解答:调用过程MAX-HEAPIFY的前提是左堆和右堆都是最大堆,所以要从树叶到根。

6.3-3 解答:待完成。

6.4-1 解答:待完成。

6.4-2 解答:待完成。

6.4-3 解答:待完成。

6.4-4 解答:待完成。

6.4-5 解答:待完成。

6.5-1 解答:待完成。

6.5-2 解答:待完成。

6.5-3 解答:待完成。

6.5-4 解答:待完成。

6.5-5 解答:待完成。

6.5-6 解答:待完成。

6.5-7 解答:待完成。

6.5-8 解答:待完成。

6.5-9 解答:待完成。

思考题

待完成。