猪脚说第十一期

• 本期内容为补充内容。

• 以伪代码形式说明，规定数组下标从 1 开始。

如何证明算法的正确性

我们以插入排序算法为例，假设我们有数组A = {5, 2, 4, 6, 1, 3}，

此算法的伪代码如下

INSERTION-SORT(A):
	for j = 2 -> A.length
		temp = A[j]
		// i 用于寻找 temp 应插入的位置
		i = j - 1
		while i > 0 && A[i] > temp
			A[i + 1] = A[i]
			i = i - 1
		A[i + 1] = temp

我们知道，在最外层for循环每次迭代的开始，子数组A[1...j-1]构成了当前已经排好的序列，这个特性也被称为循环不变式。我们可以证明这个性质将一直保持下去，直到循环结束。具体而言，我们需要证明如下三点

• 初始化：循环开始之前，该条件为真。
• 保持：如果循环的某次迭代之前该条件为真，那么下次迭代之前它仍为真。
• 终止：循环终止时，这个条件能够说明算法达到我们想要的目的。

对于上述插入排序算法，证明如下

• 初始化：第一次循环之前，j = 2，子序列仅由A[1]单个元素构成，它是已经排好序的，故条件成立。
• 保持：假设A[1...j-1]已经排好序，在循环体内，代码的 5 ～ 8 行将A[j - 1] A[j - 2] A[j - 3]等依次向右移动，直到找到了A[j]应该插入的位置并将其插入。此时，子序列A[1...j]中的元素仍然不变，但是这个序列已经排好序了，说明循环不变式的条件得以保持。
• 终止：循环终止的条件是j > A.length。由于每次循环后j会加 1，所以循环终止时j = A.length + 1。代入循环不变式，子序列A[1...A.length]由原来A中的元素组成，但是已经排好序了，**由于整个数组就是子序列A[1...A.length]**，所以整个数组已经排好序。故算法正确。

循环不变量的思路类似于数学归纳法，当然，这里的归纳在达到数据规模 $n$ 时就终止了。

堆

基本概念

堆（heap）是这样一棵完全二叉树，它除了根结点外，所有结点都满足性质结点值大于等于父结点的值或结点值小于等于父结点的值，这两种堆分别称最小堆和最大堆。堆必然要用数组存储，这样便于高效地编程。设数组为A，A.length表示数组元素个数，A.heap-size表示堆中的元素个数 —— 之所以要区分这两者，是因为在某个时刻，可能只有A[1...A.heap-size]这一段子序列满足堆的性质。

根据完全二叉树的性质，不难得出

PARENT(i):
	return i / 2
LEFT(i):
	return 2 * i
RIGHT(i):
	return 2 * i + 1

维护堆的性质

heapify 是 heap 的动词形式，可以表示“使堆化、维护堆的性质”。我们通过调用HEAPIFY(A, i)，来使得以下标i为根结点的子树满足堆的性质。

HEAPIFY(A, i):
	left = LEFT(i)
	right = RIGHT(i)
	if left <= A.heap-size && A[left] > A[i]
		largest = left
	else largest = i
	if right <= A.heap-size && A[right] >= A[largest]
		largest = right
	if largest != i
		exchange A[i] <-> A[largest]
		HEAPIFY(A, largest)

在这个函数中，我们先获取了以i为下标的结点的左孩子和右孩子的下标，然后，找出了最大的那个结点的下标并存于largest。如果largest不是i，说明此时子树i不满足堆的性质，于是我们把那个比较大的结点和i对换，并递归地维护子树的性质；如果largest就是i，说明堆的性质已经满足，函数结束。

建堆

BUILD-HEAP(A):
	A.heap-size = A.length
	for i = A.length / 2 -> 1
		HEAPIFY(A, i)

这个函数中的for循环，自底向上地把数组A转化成一个最大堆。我们严格地证明这个过程。

循环不变量：每一次for循环的开始，结点i + 1，i + 2，… ，A.length都是一个最大堆的根结点。

• 初始化：在第一次循环前，i = A.length / 2，这是最后一个叶结点的父结点的下标。因此i + 1，… ，A.length都是叶结点，它们都是平凡最大堆（仅有一个结点的堆）的根结点。
• 保持：结点i的孩子结点的下标都比i大，根据循环不变量，它们都是最大堆的根。调用HEAPIFY后，i也成为了最大堆的根，于是循环不变量得以保持。
• 终止：循环终止时，i = 0。根据循环不变量，结点1，2，… ，A.length都是最大堆的根，特别，结点1就是整个堆的根。于是我们正确地构造了最大堆A[1...A.length]。

堆排序

HEAP-SORT(A):
	BUILD-HEAP(A)
	for i = A.length -> 2
		exchange A[1] <-> A[i]
		A.heap-size = A.heap-size - 1
		HEAPIFY(A, 1)

我们直观地理解这个过程，首先建堆，此时A[1]必为数组最大元素，开始循环，将A[1]放到最后，则数组中最大的元素已经安置好。此后我们将堆的规模减 1 并再次HEAPIFY，则数组中第二大的元素来到A[1]的位置，再将其放到倒数第二的位置……这样我们就实现了A从小到大排序。

优先队列

堆排序是一个优秀的算法，但实际上快速排序的性能通常优于堆排序。但是，我们进一步思考堆的构建和维护过程，在这个过程中，我们始终维护着最大（最小）的那个元素的位置。

假如我们要获取数组中的最大元素，往往需要遍历该数组（或排序）。但是假如数组的元素不断变化，则每一次都要进行遍历 / 排序操作，这一操作的开销是很大的。事实上，如果我们只关心最大的那个元素是多少，利用堆的性质可以更高效地解决这个问题。

优先队列是一种特殊的线性表，具有最高优先级的元素位于队头，优先出队。显然，利用堆可以解决这个问题。优先队列的常见操作有

• 插入一个元素
• 获取队头元素
• 出队
• 修改某个元素的值

每一次操作后，我们都需要利用HEAPIFY的算法，使得具有最高优先级的那个元素来到队头。

“最高优先级”问题在很多领域均有涉及，因此优先队列是非常重要的数据结构。很多编程语言都高效地封装了优先队列，以方便编程者使用。例如在 C++ 中

#include <iostream>            // #include <stdio.h>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pq;
    // 定义了能容纳 int 类型的优先队列，默认队头为最大元素
    int num;
    while (cin >> num) {  // while (scanf("%d", &num) != EOF)
        pq.push(num);     // 入队
    }
    while (!pq.empty()) {
        cout << pq.top() << endl; // printf("%d\n", pq.top());
        pq.pop();         // 出队
    }
    return 0;
}

当然，对于我们自定义的复合数据结构，我们还需要自己声明一套比较规则进行排序。

请思考：qsort函数的cmp是怎么实现的？什么是函数指针？我们自己写的排序函数能多加一个cmp参数以便自定义任何规则的排序吗？

Author: Riccardo, diandian