算法导论第 6 章：堆排序

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

主要内容

本章介绍堆排序（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)\)