算法导论第 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)\)

需要知道,树的高度深度分别定义如下:

  • 高度:节点的高度为从该节点到一片树叶的最长路径的长度,所有树叶的高度为0
  • 深度:节点的深度为从根到该节点的唯一路径长,根的深度为0

维护堆的性质

下面的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
16
// 打印数组内容
void PrintArray(int arr[], int start, int end)
{
for (int i = start; i <= end; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

void TestHeapSort()
{
int A[11] = {-1, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
PrintArray(A, 1, 10);
HeapSort(A, 10);
PrintArray(A, 1, 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-3 解答:则此时满足最大堆性质,数组不会有任何修改。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void MaxHeapify(Heap *hp, int root)
{
while (root <= hp->heap_size) {
int left = LEFT(root);
int right = RIGHT(root);
int 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;
}
if (largest == root) {
break;
}

Exch(hp->data, root, largest);
root = largest;
}
}

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

6.3-3 解答:可以用归纳法证明,当\(h=0\)时,叶子节点最多有\(\lceil n/2^{h+1} \rceil\)个,成立;当高度为\(t\)的节点有\(\lceil n/2^{t+1} \rceil\)个,则高度为\(t+1\)的节点个数最多是它的一半,为\(\lceil n/2^{t+2} \rceil\);所以,得证。

6.4-2 解答:利用循环不变量证明算法的正确性,略。

6.4-3 解答:如果是升序排列,第1行构建最大堆耗费时间为\(\Theta(n \lg n)\),第5行耗费时间\(\Theta(\lg n)\),整个循环过程耗时\(\Theta(n \lg n)\),总的耗费时间为\(\Theta(n \lg n)\);如果是降序排列,由于此时MAX-HEAPIFY仅耗费常数时间,所以第一行构建最大堆耗费时间为\(\Theta(n)\),循环过程依然耗费时间\(\Theta(n \lg n)\),所以总的时间也为\(\Theta(n \lg n)\)

6.4-4 解答:6.4.3已经表明了这一点。

6.5-4 解答:把关键字设置为\(-\infty\)能够确保把它放在数组末尾的位置能够满足最大堆序性质,可以避免多余的操作。

6.5-5 解答:通过循环不变量证明算法的正确性,略。

6.5-6 解答:该过程的代码可以修改为:

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;
}

// 避免交换操作,借鉴插入排序的做法
while (idx > 1 && hp->data[PARENT(idx)] < key) {
hp->data[idx] = hp->data[PARENT(idx)];
idx = PARENT(idx);
}
hp->data[idx] = key;
}

6.5-7 解答:实现先进先出的队列,入队操作通过MAX-HEAP-INSERT完成,先入队的元素关键字大,后入队的关键字依次减小,出队操作通过HEAP-EXTRACT-MAX完成;实现堆栈,入队操作通过MAX-HEAP-INSERT完成,先入队的元素关键字小,后入队的关键字依次增大,出队操作通过HEAP-EXTRACT-MAX完成。

6.5-8 解答:用最后一个元素替补被删除的节点,将堆的大小减一,重新保持堆序性质,代码如下:

1
2
3
4
5
6
void MaxHeapDelete(Heap *hp, int idx)
{
hp->data[idx] = hp->data[hp->heap_size];
hp->heap_size--;
MaxHeapify(hp, idx);
}

6.5-9 解答:将每个链表的值依次插入到堆中,然后将堆中的元素一个个蹦出来。

思考题

6-1 (用插入的方法建堆) 可以通过反复调用MAX-HEAP-INSERT实现向一个堆中插入元素。请问:

  1. 当输入数据相同时,两种方法生成的堆是否总是一样?如果是,请证明;否则,请举出一个反例。 解答:不相同,比如输入序列为为1、 2、 3,用前面的方法建堆得到3、2、1,用插入的方法得到3、1、2
  2. 证明:在最坏情况下,用插入的方法建立包含\(n\)个元素的堆的时间复杂度为\(\Theta(n \lg n)\)。 解答:MAX-HEAP-INSERT要调用HEAP-INSERT-KEY,它的复杂度为\(\Theta(\lg n)\),调用\(n\)MAX-HEAP-INSERT,所以复杂度为\(\Theta(n \lg n)\)

6-2 (对d叉堆的分析) d叉堆与二叉堆很类似,但(一个可能的例外是)其中的每个非叶节点有\(d\)个孩子,而不是仅仅2个。

  1. 如何在一个数组中表示一个d叉堆? 解答:将数组的位置0作为根节点,节点\(i\)的父节点在位置\(\lfloor (i-1)/d \rfloor\)\(d\)个孩子节点位置从\(di+1\)\(di+d\)
  2. 包含\(n\)个元素的d叉堆的高度是多少?请用\(n\)\(d\)表示。 解答:\(\lceil \log_d n \rceil\)
  3. 请给出EXTRACT-MAX在d叉最大堆上的一个有效实现,并用\(d\)\(n\)表示出它的时间复杂度。 解答:和二叉堆类似,时间复杂度为\(O(d \log_d n)\)
  4. 给出INSERT在d叉最大堆上的一个有效实现,并用\(d\)\(n\)表示出它的时间复杂度。 解答:和二叉堆类似,时间复杂度为\(O(\log_d n)\)
  5. 给出INCREASE-KEY(A, i, k)的一个有效实现。当\(k < A[i]\)时,它会触发一个错误,否则执行\(A[i]=k\),并更新相应的d叉最大堆。请用\(d\)\(n\)表示出它的时间复杂度。 解答:和二叉堆类似,时间复杂度为\(O(\log_d n)\)