堆排序与优先队列
堆排序与优先队列
【注】参考自教材「算法导论」。
1. 堆
1.1 定义
（二叉）堆物理上是一个数组，逻辑上是一棵完全二叉树，树上的每一个结点对应数组中的一个元素。 设表示堆的数组 A，其包含两个属性：
- A.length 给出数组元素的个数。
- A.heapsize给出有多少个堆元素存储在该数组中。
1.2 性
从根结点编号为 1 开始，同一深度的结点自左往右、不同深度的结点自上往下，对堆上的结点编号（即逐层从左往右进行编号），结点编号对应数组 A 中元素的下标。
- n 个元素的堆的高度为 ⌊lgn⌋ 因为堆是一棵完全二叉树，设堆高为h，则 \begin{array}{c} 2^h \leq n \leq 2^{h+1} - 1 \Rightarrow \lg (n+1) - 1 \leq h \leq \lg n \\ \Rightarrow \lg n - 1 \lt \lg (n+1) - 1 \leq h \leq \lg n \end{array}
因为 h为整数，故 h=⌊lgn⌋ 。
- 非根结点 i的双亲结点的编号为
\begin{array}{c} parent[i] = \lfloor i/2 \rfloor \end{array}
- 非叶结点 i的左右孩子结点编号分别为
\begin{array}{c} left[i] = 2i \\ right[i] = 2i + 1 \end{array}
- 当用数组表示存储 n 个元素的堆时，叶结点编号分别是 \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots, n 。
证明 因为 n 是编号最大的结点，故 n 肯定是叶结点，且是编号最大的叶结点。故 n 的双亲 parent[n] = \lfloor n/2 \rfloor也是编号最大的非叶结点。故区间 (parent[n], n]范围内的结点编号都是叶结点。即 \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots,
- 对于包含 n 个元素的堆最多包含 \lceil n/2^{h+1} \rceil 个高度为 h 的结点。
证明 归纳法证明如下：
- 对于高度为 0 的结点（即叶结点），因为堆是一棵完全二叉树，故叶结点个数 l 满足 l_0 = \lfloor (n+1)/2 \rfloor = \lceil n/2^{0 + 1} \rceil 。
- 假设对于高度为 h 的结点，满足结点数l_h = \lceil n/2^{h+1} \rceil，由于堆是一棵完全二叉树，故对于高度为 h+1的结点，有
\begin{array}{c} l_{h+1} = \lceil l_h / 2 \rceil = \lceil n / 2^{(h+1)+1} \rceil \end{array}
堆可分为最大堆和最小堆，二者分别满足最大堆性质和最小堆性质。
- 最大堆性质：除了根结点以外的所有结点 i 满足
\begin{array}{c} A[parent(i)] \geq A[i] \end{array}
- 最小堆性质：除了根结点以外的所有结点 i满足
\begin{array}{c} A[parent(i)] \leq A[i] \end{array}
2. 堆排序
堆排序是原址的、不稳定的。以下仅以最大堆为例。
2.1 maxHeapify
该过程用于维护最大堆性质。即根据输入的结点 iii 维护以 iii 为根的堆的最大堆性质。
// 伪代码
maxHeapify(A, i) {
l = left(i) // 左孩子结点
r = right(i) // 右孩子结点
largest = i // 记录左孩子、右孩子、根三者中值最大的一者
if l ≤ A.heapsize and A[l] > A[largest]
largest = l
if r ≤ A.heapsize and A[r] > A[largest]
largest = r
if largest != i
swap(A[i], A[largest])
maxHeapify(A, largest)
}由于堆高为 ⌊lgn⌋，故 maxHeapify 复杂度为 O(lgn)。
2.2 buildMaxHeap
采用自底向上的方法，利用 maxHeapify 过程，将数组 A 构建为一棵最大堆。即从最小的非空子树（内部结点）开始，由于最小非空子树最少两个元素、最多三个元素，故 maxHeapify 后一定是一棵最大堆，然后逐步向上对更大的子树递归利用 maxHeapify 构建最大堆。 根据上文堆的性质可知，堆的叶结点编号分别是 \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots, n ，故非叶结点的编号为 1,2, \cdots, \lfloor n/2 \rfloor
// 伪代码
buildMaxHeap(A) {
A.heapsize = A.length
for i = ⌊A.heapsize/2⌋ downto 1
maxHeapify(A, i)
}因为在高度为 h的树上执行 maxHeapify 过程的复杂度为 O(h)，而由上文堆的性质可知，堆中高度为h 的结点数为 \lceil n/2^{h+1} \rceil，堆的高度为\lg n，故 buildMaxHeap 的复杂度为
\begin{array}{c} \sum^{\lfloor \lg n \rfloor}_{h = 0}\lceil n/2^{h+1} \rceil O(h) = O(n) \end{array}
2.3 heapSort
构建好最大堆后，值最大的元素在 A[1]，通过将 A[1] 与 A[A.heapsize] 交换后，然后缩小 A.heapsize，并使用 maxHeapify 过程维护最大堆性质。如此往复，直到 A.heapsize = 2 时，数组 A 变为有序。
// 伪代码
heapSort(A) {
buildMaxHeap(A)
for i = A.length downto 2
swap(A[1], A[i])
A.heapsize = A.heapsize - 1
maxHeapify(A, 1)
}heapSort 的复杂度为 O(n + \lfloor \lg n \rfloor + \lfloor \lg (n-1) \rfloor + \cdots + \lfloor \lg 1 \rfloor) = O(n + \lg n!) = O(n\lg n)。
2.4 模板
#include <bits/stdc++.h>
using namespace std;
// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
return t1 < t2;
}
// 最大堆
template <typename T>
struct MaxHeap {
#ifndef _MAXHEAP_
#define _MAXHEAP_
#define ll long long
#endif
ll length;
ll heapsize;
MaxHeap() {}
// 维护最大堆性质
void maxHeapify(T *A, ll i, bool (*cmp)(const T &, const T &)) {
ll l = 2*i, r = 2*i + 1;
ll largest = i;
if(l <= heapsize && cmp(A[largest], A[l])) {
largest = l;
}
if(r <= heapsize && cmp(A[largest], A[r])) {
largest = r;
}
if(largest != i) {
swap(A[i], A[largest]);
maxHeapify(A, largest, cmp);
}
}
// 构建最大堆
void buildMaxHeap(T *A, bool(*cmp)(const T &, const T &)) {
heapsize = length;
for(ll i = heapsize/2; i; --i) {
maxHeapify(A, i, cmp);
}
}
// 堆排序
void heapSort(T *bA, T *eA, bool(*cmp)(const T &, const T &) = compare) {
T *A = bA - 1;
length = eA - bA;
buildMaxHeap(A, cmp);
for(ll i = length; i; --i) {
swap(A[1], A[i]);
heapsize--;
maxHeapify(A, 1, cmp);
}
}
};3. 优先队列
以下优先队列以最大堆为底层实现。
3.1 maxHeapifyUp
该过程用于从当前结点向根结点的路径上维护最大堆性质。
// 伪代码
maxHeapifyUp(A, i) {
p = parent(i) // 双亲结点
if p > 0 and A[p] < A[i]
swap(A[i], A[p])
maxHeapifyUp(A, p)
}由于堆高为 \lfloor \lg n \rfloor，故 maxHeapifyUp 复杂度为 O(\lg n) 。
3.2 maxHeapifyDown
该过程用于从当前结点向叶结点的路径上维护最大堆性质。
// 伪代码
maxHeapifyDown(A, i) {
l = left(i) // 左孩子结点
r = right(i) // 右孩子结点
largest = i // 记录左孩子、右孩子、根三者中值最大的一者
if l ≤ A.heapsize and A[l] > A[largest]
largest = l
if r ≤ A.heapsize and A[r] > A[largest]
largest = r
if largest != i
swap(A[i], A[largest])
maxHeapifyDown(A, largest)
}由于堆高为 \lfloor \lg n \rfloor，故 maxHeapifyDown 复杂度为O(\lg n)。
3.3 模板
#include <bits/stdc++.h>
using namespace std;
#ifndef _PRIORITYQUEUE_
#define _PRIORITYQUEUE_
#define ll long long
#define MAXN 1000005
// 比较元素
template < typename T >
struct Compare {
bool operator () (const T & a, const T & b) {
return a < b;
}
};
// 优先队列
template < typename T, typename F = struct Compare <T> >
struct PriorityQueue {
ll heapsize;
T A[MAXN];
F compare;
typedef T* iterator;
// 构造函数
PriorityQueue(): heapsize(0) {}
// 向上维护最大堆性质
void maxHeapifyUp(ll i) {
ll p = i/2;
if(p && compare(A[p], A[i])) {
swap(A[p], A[i]);
maxHeapifyUp(p);
}
}
// 向下维护最大堆性质
void maxHeapifyDown(ll i) {
ll l = 2*i, r = 2*i + 1;
ll largest = i;
if(l <= heapsize && compare(A[largest], A[l])) {
largest = l;
}
if(r <= heapsize && compare(A[largest], A[r])) {
largest = r;
}
if(largest != i) {
swap(A[i], A[largest]);
maxHeapifyDown(largest);
}
}
// 将元素压入优先队列中
void push(T a) {
A[++heapsize] = a;
maxHeapifyUp(heapsize);
}
// 将元素弹出优先队列外
T pop() {
swap(A[1], A[heapsize]);
--heapsize;
maxHeapifyDown(1);
return A[heapsize+1];
}
// 获取优先队列顶部元素
T top() {
return A[1];
}
// 获取优先队列大小
ll size() {
return heapsize;
}
// 判断优先队列是否为空
bool empty() {
return !heapsize;
}
// 清空优先队列
void clear() {
heapsize = 0;
}
// 获取优先队列首元素
T* begin() {
return &A[1];
}
// 获取优先队列尾元素
T* end() {
return &A[heapsize] + 1;
}
};
#endif