算法导论第 6 章：堆排序

发表于 分类于 Waline： 本文字数： 3.1k 阅读时长 ≈ 11 分钟

主要内容

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

堆

二叉堆一般用数组实现，可以看成是一个近似的完全二叉树，树的每个节点对应数组中的一个元素。根节点为，给定一个下标，很容易计算它的父节点、左孩子和右孩子的下标分别为，，。需注意，用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)

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

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

需要知道，树的高度和深度分别定义如下：

  • 高度：节点的高度为从该节点到一片树叶的最长路径的长度，所有树叶的高度为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);        // 以该节点为根的树可能不满足性质，递归调用
    }
}

由于每个子树的大小至多为（最坏情况发生在最底层恰好半满的时候），所以上述过程的递归式为：

根据主定理，递归式的解为，对于树高为的节点，MaxHeapify的时间复杂度为。

建堆

可以用自底向上的方法利用过程MaxHeapify把数组转换为最大堆。叶节点的下标范围是从到，每个叶节点可以看成只包含一个元素的堆。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需要调用次MaxHeapify，所以，总的时间复杂度为，但这并不是渐近紧确界。实际上，可以计算得到它的时间复杂度为，可以在线性时间内将一个无序数组构造成一个最大堆。

堆排序算法

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

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的时间复杂度为，调用了次MaxHeapify，每次时间为。所以堆排序算法的时间复杂度为。下面的测试代码展示了使用方法：

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可以在时间内完成：

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

它的时间复杂度为，因为除了时间复杂度为的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的时间复杂度为，因为在算法中，从关键字更新的节点到根节点的路径长度为。

过程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);
}

在包含个元素的堆上，MaxHeapInsert的运行时间为。

综上所述，在一个包含个元素的堆中，所有优先队列的操作都可以在时间内完成。

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

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 解答：高度为的堆中，元素最多有个，最少有个。

6.1-2 解答：根据上面的结果，高度为的堆，元素个数范围是，所以。

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

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

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

6.1-6 解答：不是。

6.1-7 解答：叶子节点没有孩子节点，即有，即，得证。

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

6.2-4 解答：当时，节点为叶节点，调用函数，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 解答：可以用归纳法证明，当时，叶子节点最多有个，成立；当高度为的节点有个，则高度为的节点个数最多是它的一半，为；所以，得证。

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

6.4-3 解答：如果是升序排列，第1行构建最大堆耗费时间为，第5行耗费时间，整个循环过程耗时，总的耗费时间为；如果是降序排列，由于此时MAX-HEAPIFY仅耗费常数时间，所以第一行构建最大堆耗费时间为，循环过程依然耗费时间，所以总的时间也为。

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

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

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. 证明：在最坏情况下，用插入的方法建立包含个元素的堆的时间复杂度为。 解答：MAX-HEAP-INSERT要调用HEAP-INSERT-KEY，它的复杂度为，调用次MAX-HEAP-INSERT，所以复杂度为。

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

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