算法分析与设计CH6：堆排序详解（文末附优先队列完整代码）

CH6：HeapSort

MindMap

Topics：

Heaps
HeapSort
Priority queue

Recap and Overview

强调稳定性时多关注的是多关键字排序。

插入排序

时间复杂度是 $O(n^2)$ ，原地排序
归并排序

时间复杂度是 $O (n l g n)$ ，需要辅助存储空间
堆排序

时间复杂度是 $\Theta(nlgn)$ ，原地排序
快排

平均情况的时间复杂度是 $O (n l g n)$ ，原地排序
线性时间的排序

6.1 Heap

6.1.1 堆存储和堆数据结构

（1）堆内存的使用

堆的使用：

内存的分类

{\begin{cases} 栈 内 存 ： 局 部 变 量 ， 方 法 和 函 数 \\ 堆 内 存 ： m a l l o c n e w \\ 静 态 方 法 区 ： 全 局 变 量 \end{cases}

⎩ ⎨ ⎧ 栈内存：局部变量，方法和函数 堆内存： ma ll oc n e w 静态方法区：全局变量

（2）堆数据结构的使用

堆数据结构：

元素按照下标索引——堆数据结构的实现是一个一维数组
每个元素支持：PARENT，LEFT和RIGHT操作
父子关系的映射逻辑为：

若数组下标从1开始，那么父子映射关系函数为：
- $\lfloor i/2 \rfloor$
- $L EFT (i) = 2 i$
- $R I G H T (i) = 2 i + 1$

若数组下标从0开始，那么父子映射关系函数为：

$\lceil i/2 \rceil -1$
$L EFT (i) = 2 i + 1$
$R I G H T (i) = 2 i + 2$
```
int getParent(int child) {
	return ceil(child / 2.0) - 1;
}

int getLeft(int parent) {
	return parent * 2 + 1;
}

int getRight(int parent) {
	return parent * 2 + 2;
}
1
2
3
4
5
6
7
8
9
10
11
```
堆中父子的大小关系

${\begin{cases} 大顶堆： A [P A R E N T (i)] \geq A [i] \\ 小顶堆： A [P A R E N T (i)] \leq A [i] \end{cases}$ ${大顶堆： A [P A RENT (i)] \geq A [i] 小顶堆： A [P A RENT (i)] \leq A [i]$
堆中的第一个元素是 $A [0]$ 或者 $A [1]$ ，对应两种不同的情况

结点的高度是从该结点到叶子结点的最长路径。

堆的高度是树根的高度。

叶子结点的高度为0，树根的高度为树的高度。

有n个结点的树的高度为 $\lfloor lgn\rfloor$

（3）时间复杂度概述

MAX-HEAPIFY：保证堆是一个大顶堆，时间复杂度是 $O (l g n)$

Build-Max-Heap：建堆，时间复杂度是 $O (n)$

堆排序：堆排序时，我们首先要建成一个大顶堆，然后反复执行，取下结点后调用MAX-HEAPIFY的过程，时间复杂度是 $O (n l g n)$

6.1.2 堆的建立

建堆两种方式：递归建堆和非递归建堆

（1）递归建堆

递归建堆三个步骤：分、治、合并

分：分解成子树
治：递归处理左子树和右子树
合并：MaxHeapify

void buildMaxHeap(int parent, vector<int>& vec) {
	if (parent < vec.size()) {// 考虑是否还有孩子结点
		// 分 
		int left = getLeft(parent);
		int right = getRight(parent);
		// 治 
		buildMaxHeap(left, vec);
		buildMaxHeap(right, vec);
		// 合并 
		maxHeapify(vec, parent);
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12

（2）非递归建堆

非递归建堆过程采用循环的建堆方式，从最后一个非叶子结点开始，逐步建堆

最后一个非叶子结点的下标： $\lfloor vec.size()/2\rfloor$

void buildMaxHeap_iteration(vector<int>& vec) {
	int last_non_leaf = vec.size() / 2;
	for (int i = last_non_leaf; i >= 0; i--) {
		maxHeapify(vec, i);
	}
} 
1
2
3
4
5
6

（3）合并过程：`MAXHEAPIFY`

MaxHeapify()时间复杂度为 $O (h)$ ，其中 $h$ 是树的高度，$h = \lfloor lgn \rfloor $

递归写法

写成递归处理的形式如下：

void maxHeapify(vector<int>& vec, int parent) {
	int largest = parent;
	int left = getLeft(parent);
	int right = getRight(parent);
	// 找到父子之间最大值的位置 
	if (left < vec.size() && vec[left] > vec[largest]) {		// 注意短路判决 
		largest = left;
	}
	if (right < vec.size() && vec[right] > vec[largest]) {    	// 注意短路判决 
		largest = right;
	}
	// 更换位置
	if (largest != parent) {
		int temp = vec[largest];
		vec[largest] = vec[parent];
		vec[parent] = temp;
		// 接着maxheapify处理子树
		maxHeapify(vec, largest); 
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

循环写法

上述的写法是在结束的时候调用递归处理，这种写法很容易改成循环的形式。如下：

void maxHeapify(vector<int>& vec, int parent) {
    int largest = parent;
    bool ifChange = true;
    while(ifChange) {
        int left = getLeft(parent);
		int right = getRight(parent);
        // 找到父子之间最大值的位置 
        if (left < vec.size() && vec[left] > vec[largest]) {		// 注意短路判决 
            largest = left;
        }
        if (right < vec.size() && vec[right] > vec[largest]) {    	// 注意短路判决 
            largest = right;
        }
        // 更换位置
        if (largest != parent) {		// 需要交换
            int temp = vec[largest];
            vec[largest] = vec[parent];
            vec[parent] = temp;
            ifChange = true;
        }else{
            ifChange = false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（4）运行时间分析

若采取直接的方式分析运行时间，那么时间将会是：
$O(n/2)\times O(lgn) = O(nlgn)$
key observation：

$T (n) = 2 T (n /2) + O (l g n)$
$O(n^{log_2^2-\epsilon})=O(n^{1-\epsilon})$

所以堆排序的时间复杂度为 $\Theta(n)$

6.1.3 堆排序

堆排序策略：每次取出堆顶的元素，使用堆中最后一个元素与堆顶元素交换，然后调用MaxHeapify

void HeapSort(vector<int>& vec) {
	int size = vec.size();	// 从0开始的 
	for (int i = size - 1; i >= 1; i--) {	// 从最后一个结点开始 
		int temp = vec[i];
		vec[i] = vec[0];
		vec[0] = temp;
		size = size - 1;
		maxHeapify(vec, 0, size);
	}
	
}
1
2
3
4
5
6
7
8
9
10
11

时间复杂度： $O (n l g n)$
原地排序 inplace
不稳定排序

6.2 PriorityQueue

6.2.1 应用

最大值优先队列的应用：

在共享计算机上调度工作
实现优先队列

最小值优先队列应用：

迪杰特斯拉算法
Prim 最小生成树算法
哈夫曼编码

6.2.2 优先队列

操作：

插入一个元素Insert(S, x)
获得最大值MAXIMUM(S)
取出最大值EXTRACT-MAX(S)
INCREASE-KEYS(S, x, k)

将位置x的元素正大为key

（1）获得最大元素

MAXMUM(A)
    return A[0];
1
2

（2）去除最大元素

先检查溢出
最后一个元素与第一个元素交换
maxHeapify调整

int PriorityQueue::extract_max() {
	if (vec.size() < 1) {
		cout << "Error：HEAP UNDERFLOW" << endl;
		return 0;
	} 
	int max = vec[0];	// 需要返回的值 
	vec[0] = vec[vec.size() - 1];	// 与最后一个元素交换
	vec.pop_back();		// 弹出最后一个元素 
	maxHeapify(vec.size(), 0);
	return max;
}
1
2
3
4
5
6
7
8
9
10
11

（3）增大元素

首先判断是否是增大
一直和父亲换，直到父亲的值更大

void PriorityQueue::increase_key(int index, int key) {
	if (key < vec[index]) {
		cout << "Error：" <<key << "is smaller than the original number " << vec[index] << endl;
	}
	vec[index] = key;
	while (index > 0 && vec[parent(index)] < vec[index]) {
		int temp = vec[index];
		vec[index] = vec[parent(index)];
		vec[parent(index)] = temp;
		index = parent(index); 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

（4）插入元素

堆大小加一
将末尾元素设置为无穷小
调用增大元素的函数进行处理

void PriorityQueue::insert(int key) {
	// 放到最后
	vec.push_back(key); 
	// 向上比较调整
	increase_key(vec.size()-1, key); 
}
1
2
3
4
5
6

优先队列完整代码如下：

#include
#include
#include

using namespace std;

class PriorityQueue {
public:
	// 构造函数 
	PriorityQueue () = default;
	PriorityQueue (vector<int>& paraVec);
	// 向队列中插入新的值 
	void insert (int key); 
	// 返回优先队列中的最大值 
	int maximum ();
	// 去除优先队列中的最大值并且返回 
	int extract_max ();
	// 增加index处的值，增加为key 
	void increase_key (int index, int key);
	// 堆排序
	void heapSort (); 
	// 打印出堆中的数据：
	void queuePrint(); 
	
private: 
	vector<int> vec;
	// 建堆函数
	void buildMaxHeap (int root = 0); 
	// 初始建堆的递归处理子堆
	void maxHeapify (int size, int root); 
	// 返回左孩子结点的坐标
	int leftChild (int root);
	// 返回右孩子结点的坐标
	int rightChild (int root);
	// 返回父亲结点的坐标
	int parent (int child); 
	
};

int PriorityQueue::leftChild(int root = 0) {
	return root * 2 + 1;
} 

int PriorityQueue::rightChild(int root = 0) {
	return root * 2 + 2;
}

int PriorityQueue::parent(int child) {
	return ceil(child / 2.0) - 1;	// 默认向下取整 
}

PriorityQueue::PriorityQueue (vector<int>& paraVec):vec(paraVec) {
	buildMaxHeap();	// 初始时直接将输入的数组转换为大顶堆 
};

void PriorityQueue::buildMaxHeap(int root) {
	if (root < vec.size()) {
		// 分 
		int left =  leftChild(root);
		int right = rightChild(root);
		// 治
		buildMaxHeap(left);
		buildMaxHeap(right);
		// 合并
		maxHeapify(vec.size(), root); 		
	}
}

void PriorityQueue::maxHeapify(int size, int root) {
	int left = leftChild(root);
	int right = rightChild(root);
	int largest = root;
	// 找到三者中较大的一个
	if (left < size && vec[left] > vec[largest]) {
		largest = left;
	}
	if (right < size && vec[right] > vec[largest]) {
		largest = right;
	}
	if (largest != root) {	// 需要将root的值与largest的值进行交换
	 	int temp = vec[root];
		vec[root] = vec[largest];
		vec[largest] = temp;	// 交换完毕
		maxHeapify(size, largest);	// largest处现在是换下来的root的值，需要对这个子树进行处理 
	}
}

void PriorityQueue::heapSort() {
	buildMaxHeap();
	int size = vec.size();
	for (int i = size - 1; i >= 1; i--) {	// 从最后一个结点开始 
		int temp = vec[i];
		vec[i] = vec[0];
		vec[0] = temp;
		size = size - 1;
		maxHeapify(size, 0);
	}
}

void PriorityQueue::queuePrint() {
	int k = 1, n = 1;
	for (int i = 0; i < vec.size(); i++,k++) {
		cout << vec[i] << " ";
		if(k == n) {
			cout << endl;
			k = 0;
			n = n * 2;
		}
	}
	cout << endl;
}

int PriorityQueue::maximum() {
	return vec[0];
}

int PriorityQueue::extract_max() {
	if (vec.size() < 1) {
		cout << "Error：HEAP UNDERFLOW" << endl;
		return 0;
	} 
	int max = vec[0];	// 需要返回的值 
	vec[0] = vec[vec.size() - 1];	// 与最后一个元素交换
	vec.pop_back();		// 弹出最后一个元素 
	maxHeapify(vec.size(), 0);
	return max;
}

void PriorityQueue::increase_key(int index, int key) {
	if (key < vec[index]) {
		cout << "Error：" <<key << "is smaller than the original number " << vec[index] << endl;
	}
	vec[index] = key;
	while (index > 0 && vec[parent(index)] < vec[index]) {
		int temp = vec[index];
		vec[index] = vec[parent(index)];
		vec[parent(index)] = temp;
		index = parent(index); 
	}
}

void PriorityQueue::insert(int key) {
	// 放到最后
	vec.push_back(key); 
	// 向上比较调整
	increase_key(vec.size()-1, key); 
}


int main () {
	vector<int> vec = {4,1,3,2,16,9,10,14,8,7};
	PriorityQueue myQueue = PriorityQueue(vec);
	// 打印出初始的堆
	cout << "The original heap is："<<endl;;
	myQueue.queuePrint(); 
	// 向堆中插入元素
	myQueue.insert(11);
	// 将堆中元素变大 
	myQueue.increase_key(4,15);
	// 取出堆中最大元素
	cout << "The max number after increasing in priority queue is：" << myQueue.maximum() << endl;
	// 取出堆中的最大的元素
	myQueue.extract_max();
	// 打印取出后的结果
	cout << "The result after the max is remove："<<endl; 
	myQueue.queuePrint();
	// 堆排序
	myQueue.heapSort();
	// 打印原地排序的结果
	cout << "After HeapSort："<<endl;
	myQueue.queuePrint(); 
	
	return 0;
}
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

相关阅读:
1.5 编写自定位ShellCode弹窗
R语言Sys.Date函数获取当前日期、抽取日期数据中的年、月、日信息、日期在周内第几天、年内第多少天
JavaScript常用事件详情
凑钱（贪心算法）
【BOOST C++ 12 函数式编程】（4） Boost.Ref
被玩坏的数组排序之sort函数
Linux 下搭建 Hadoop 环境
vue3中emit(‘update:modelValue‘)使用
基于51单片机万年历设计—显示温度农历
List集合

原文地址：https://blog.csdn.net/weixin_45745854/article/details/126166203