堆排序与优先队列

【注】参考自教材「算法导论」。

1. 堆

1.1 定义

(二叉)堆物理上是一个数组,逻辑上是一棵完全二叉树,树上的每一个结点对应数组中的一个元素。
设表示堆的数组 AA,其包含两个属性:

  1. A.lengthA.length 给出数组元素的个数。
  2. A.heapsizeA.heapsize 给出有多少个堆元素存储在该数组中。

1.2 性质

从根结点编号为 1 开始,同一深度的结点自左往右、不同深度的结点自上往下,对堆上的结点编号(即逐层从左往右进行编号),结点编号对应数组 AA 中元素的下标。

  • nn 个元素的堆的高度为 lgn\lfloor \lg n \rfloor

证明
  因为堆是一棵完全二叉树,设堆高为 hh,则

2hn2h+11lg(n+1)1hlgnlgn1<lg(n+1)1hlgn\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}

因为 hh 为整数,故 h=lgnh = \lfloor \lg n \rfloor

  • 非根结点 ii 的双亲结点的编号为

parent[i]=i/2\begin{array}{c} parent[i] = \lfloor i/2 \rfloor \end{array}

  • 非叶结点 ii 的左右孩子结点编号分别为

left[i]=2iright[i]=2i+1\begin{array}{c} left[i] = 2i \\ right[i] = 2i + 1 \end{array}

  • 当用数组表示存储 nn 个元素的堆时,叶结点编号分别是 n/2+1,n/2+2,,n \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots, n

证明
  因为 nn 是编号最大的结点,故 nn 肯定是叶结点,且是编号最大的叶结点。故 nn 的双亲 parent[n]=n/2parent[n] = \lfloor n/2 \rfloor 也是编号最大的非叶结点。故区间 (parent[n],n](parent[n], n] 范围内的结点编号都是叶结点。即 n/2+1,n/2+2,,n \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots, n

  • 对于包含 nn 个元素的堆最多包含 n/2h+1\lceil n/2^{h+1} \rceil 个高度为 hh 的结点。

证明
归纳法证明如下:

  • 对于高度为 0 的结点(即叶结点),因为堆是一棵完全二叉树,故叶结点个数 ll 满足 l0=(n+1)/2=n/20+1 l_0 = \lfloor (n+1)/2 \rfloor = \lceil n/2^{0 + 1} \rceil
  • 假设对于高度为 hh 的结点,满足结点数 lh=n/2h+1l_h = \lceil n/2^{h+1} \rceil,由于堆是一棵完全二叉树,故对于高度为 h+1h+1 的结点,有

lh+1=lh/2=n/2(h+1)+1\begin{array}{c} l_{h+1} = \lceil l_h / 2 \rceil = \lceil n / 2^{(h+1)+1} \rceil \end{array}

堆可分为最大堆和最小堆,二者分别满足最大堆性质和最小堆性质。

  • 最大堆性质:除了根结点以外的所有结点 ii 满足

A[parent(i)]A[i]\begin{array}{c} A[parent(i)] \geq A[i] \end{array}

  • 最小堆性质:除了根结点以外的所有结点 ii 满足

A[parent(i)]A[i]\begin{array}{c} A[parent(i)] \leq A[i] \end{array}

2. 堆排序

堆排序是原址的、不稳定的。以下仅以最大堆为例。

2.1 maxHeapify

该过程用于维护最大堆性质。即根据输入的结点 ii 维护以 ii 为根的堆的最大堆性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 伪代码
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\lfloor \lg n \rfloor,故 maxHeapify 复杂度为 O(lgn)O(\lg n)

2.2 buildMaxHeap

采用自底向上的方法,利用 maxHeapify 过程,将数组 A 构建为一棵最大堆。即从最小的非空子树(内部结点)开始,由于最小非空子树最少两个元素、最多三个元素,故 maxHeapify 后一定是一棵最大堆,然后逐步向上对更大的子树递归利用 maxHeapify 构建最大堆。
根据上文堆的性质可知,堆的叶结点编号分别是 n/2+1,n/2+2,,n \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots, n ,故非叶结点的编号为 1,2,,n/2 1,2, \cdots, \lfloor n/2 \rfloor

1
2
3
4
5
6
// 伪代码
buildMaxHeap(A) {
A.heapsize = A.length
for i = ⌊A.heapsize/2⌋ downto 1
maxHeapify(A, i)
}

因为在高度为 hh 的树上执行 maxHeapify 过程的复杂度为 O(h)O(h),而由上文堆的性质可知,堆中高度为 hh 的结点数为 n/2h+1\lceil n/2^{h+1} \rceil,堆的高度为 lgn\lg n,故 buildMaxHeap 的复杂度为

h=0lgnn/2h+1O(h)=O(n)\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 变为有序。

1
2
3
4
5
6
7
8
// 伪代码
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+lgn+lg(n1)++lg1)=O(n+lgn!)=O(nlgn)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 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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

该过程用于从当前结点向根结点的路径上维护最大堆性质。

1
2
3
4
5
6
7
// 伪代码
maxHeapifyUp(A, i) {
p = parent(i) // 双亲结点
if p > 0 and A[p] < A[i]
swap(A[i], A[p])
maxHeapifyUp(A, p)
}

由于堆高为 lgn\lfloor \lg n \rfloor,故 maxHeapifyUp 复杂度为 O(lgn)O(\lg n)

3.2 maxHeapifyDown

该过程用于从当前结点向叶结点的路径上维护最大堆性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 伪代码
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)
}

由于堆高为 lgn\lfloor \lg n \rfloor,故 maxHeapifyDown 复杂度为 O(lgn)O(\lg n)

3.3 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#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

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!