《算法导论》笔记2-6

排序和顺序统计量

堆排序

（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树（除了最底层，该树是完全满的，而且是从左到右填充）。

表示堆的数组 A 包括两个属性：

• A.length（通常）给出数组元素的个数。
• A.heap_size 表示有多少个堆元素存储在该数组中。
  也就是说，虽然 A[A.length] 可能都存有数据，但只有 A[A.heap_size] 中存放的是堆的有效元素。（0 <= heap_size <= length）

下标： 0  1  2  3  4  5  6  7  8  9
数组：16 14 10  8  7  9  3  2  4  1

        16
    14     10
  8    7  9   3
2  4 1

树的根节点是 A[0]，这样，给定一个节点的下标 i，就很容易得到它的父节点、左孩子和右孩子：

parent(i)
	return [i/2]

left(i)
	return 2i + 1

right(i)
	return 2(i + 1)

维护最大堆的性质

max_heapify 是用于维护最大堆性质的重要过程，如果父节点 A[i] 小于其左右孩子，就违背了最大堆的性质。max_heapify 通过让 A[i] 的值在最大堆中逐级下降，从而使得以下标 i 为根节点的子树重新遵循最大堆的性质。

伪代码：

max_heapify(A, i)
	lChild = left(i)
	rChild = right(i)
	# 如果左孩子比父节点大
	if lChild <= A.heap_size and A[lChild] > A[i]
		largest = lChild
	else
		largest = i
	# 如果右孩子比左孩子 或 父节点大
	if rChild <= A.heap_size and A[rChild] > A[largest]
		largest = rChild
	# 最大节点不是父节点，要逐级下降
	if largest != i
		swap(A[i], A[largest])
		max_heapify(A, largest)

建堆

我们可以用过程 max_heapify 自底向上地把一个大小为 n = A.length 的数组转换为最大堆。其中子数组 A[[n/2] + 1 … n] 中的元素都是树的叶节点，而每个叶节点都可以看成只包含一个元素的堆，所以自底向上就是从这些叶节点的父节点开始到根节点的过程。

伪代码：

build_max_heap(A)
	A.heap_size = A.length
	for i in range(0, [A.length/2], -1)
		max_heapify(A, i)

堆排序

步骤：

1. 将输入的数组 A[n] 建成最大堆（n = A.length）。
2. 最大值总在根节点 A[0]，将 A[0] 和 A[n] 交换（即放到末尾），同时通过降低堆顶 heap_size，从而减小堆大小。
3. 调整堆，使其符合最大堆性质。
4. 不断重复 2~3 步，直到堆的大小从 n - 1 降到 1。

伪代码：

heap_sort(A)
	build_max_heap(A)
	for i in (1, A.heap_size, -1)
		swap(A[0], A[i])
		A.heap_size--
		max_heapify(A, 0)

Java 代码：

class MaxHeap {
	int[] A;
	int heapSize;
	int length;

	MaxHeap(int[] A) {
		this.A = A;
		this.length = A.length - 1;
		this.heapSize = this.length;
	}

	int parent(int i) {
		return i / 2;
	}

	int left(int i) {
		return 2 * i + 1;
	}

	int right(int i) {
		return 2 * (i + 1);
	}
}

void swap(MaxHeap heap, int i, int j) {
	int tmp = heap.A[i];
	heap.A[i] = heap.A[j];
	heap.A[j] = tmp;
}

void maxHeapify(MaxHeap heap, int i) {
	int lChild = heap.left(i);
	int rChild = heap.right(i);
	int lagest = i;
	if (lChild <= heap.heapSize && heap.A[lChild] > heap.A[i]) {
		lagest = lChild;
	}
	if (rChild <= heap.heapSize && heap.A[rChild] > heap.A[lagest]) {
		lagest = rChild;
	}
	if (lagest != i) {
		swap(heap, i, lagest);
		maxHeapify(heap, lagest);
	}
}

MaxHeap buildMaxHeap(int[] A) {
	MaxHeap heap = new MaxHeap(A);
	for (int i = heap.length / 2; i >= 0; i--) {
		maxHeapify(heap, i);
	}
	return heap;
}

int[] heapSort(int[] A) {
	MaxHeap heap = buildMaxHeap(A);
	for (int i = heap.heapSize; i >= 1; i--) {
		swap(heap, 0, i);
		heap.heapSize--;
		maxHeapify(heap, 0);
	}
	return heap.A;
}

优先队列

优先队列（priority queue）是一种用来维护由一组元素构成的集合 S 的数据结构，其中的每一个元素都有一个相关的值，称为关键字（key）。

一个最大优先队列支持以下操作：
insert(S, x)：把元素插入集合 S 中（等价于 S = S U {x}）。
max(S)：返回 S 中具有最大关键字的元素。
extract_max(S)：去掉并返回 S 中的具有最大关键字的元素。
increase_key(S, x, k)：将元素 x 的关键字值增加到 k，这里假设 k 的值不小于 x 的原关键字值。

最大优先队列的应用有很多，其中一个就是在共享计算机系统的作业调度。最大优先队列记录将要执行的各个作业以及它们之间的相对优先级，当一个作业完成或被中断后，调度器调用 extract_max 从所有的等待作业中，选出具有最高优先级的作业来执行。在任何时候，调度器可以调用 insert 把一个新作业加到队列中来。

暂略。。。