利用二叉堆实现优先级队列_在利用二叉堆实现优先级队列时,可以用一个 输入答案 来表示它,而不需要采用“列表

1 什么是优先级队列

1.1 定义

优先级队列是队列的一个重要变体，优先级最高的元素在最前，优先级最低的元素在最后。

1.2 实现方式

列表或数组的插入时间复杂度是O(n)，排序的时间复杂度是O(nlogn)，二叉堆的时间复杂度是O(logn)。因此优先级队列用二叉堆来实现。

1.3 应用

在图算法中，优先级队列是一个非常有用的数据结构。

2 二叉堆

2.1 堆

堆（Heap）是一类数据结构，它们拥有树状结构，且能够保证父节点比子节点大（或小）。大根堆，父节点比子节点大；小根堆，父节点比子节点小。

2.2 二叉堆的定义

二叉堆本质上是一种完全二叉树，其可分为最小堆和最大堆，其中最小堆的最小元素一直在队首，最大堆的最大元素一直在队首。

2.3 二叉堆的结构属性

完全二叉树有一个重要的性质，若按照层序遍历的方式给每个节点编号，并按照编号依次放入列表或数组中相应的位置，第一个位置的元素设置为0，其用途是为了后续的方法可以使用整数除法。


对于列表中处于位置i的节点，它的左子节点正好处于2i的位置，其右子节点处于位置2i+1的位置上。比如，节点编号为3的节点，其左子节点的编号为2x3，而其右子节点的编号为2x3+1。若是某节点的左节点或右节点不存在，就会超出列表的长度，比如节点编号为5的节点，2x5+1超出了列表的长度，因此其不存在右子节点。
针对Python而言，使用列表来存储，针对C++而言，可以使用vector容器来存储。

2.4 二叉堆的有序性

存储堆元素的方法依赖于堆的有序性，而堆的有序性是指：满足大根堆或小根堆的性质。

3 最小堆的C++编程实现

#include<iostream>
#include<vector>

using namespace std;
class BinaryHeap {
public:
	//新建一个空的二叉堆
	BinaryHeap() {
		this->heapVec = { 0 };
		this->currentSize = 0;
	}

	//向上移动
	void percUp(int i) {
		while (i / 2 > 0) {  //当前节点存在父节点
			if (this->heapVec[i] < this->heapVec[i / 2]) {  //若当前节点小于父节点，则交换
				int temp = this->heapVec[i / 2];
				this->heapVec[i / 2] = this->heapVec[i];
				this->heapVec[i] = temp;
			}
			i = i / 2;  //遍历父节点
		}
	}

	//往堆中插入一个新元素
	void insert(int val) {
		this->heapVec.push_back(val);
		this->currentSize++;
		percUp(currentSize); //使插入元素之后，要满足堆的性质
	}

	//返回最小的元素，元素留在堆中
	int findMin() {
		return this->heapVec[1];
	}

	//向下移动
	void percDown(int i) {
		while (2 * i <= this->currentSize) {  //当前节点存在子节点 
			int mc = minChild(i);
			if (this->heapVec[mc] < this->heapVec[i]) {
				int temp = this->heapVec[mc];
				this->heapVec[mc] = this->heapVec[i];
				this->heapVec[i] = temp;
			}
			i = mc;
		}
	}

	//返回父节点的最小子节点的索引
	int minChild(int i) {
		if (2 * i + 1 > this->currentSize) { //当前节点不存在右子节点 
			return 2 * i;
		}
		else {
			if (this->heapVec[2 * i] < this->heapVec[2 * i + 1]) {  //若左子节点小于右子节点，则返回左子节点，否则返回右子节点
				return 2 * i;
			}
			else {
				return 2 * i + 1;
			}
		}
	}

	//返回最小的元素，并将该元素从堆中删除
	int delMin() {
		int ret = heapVec[1];
		this->heapVec[1] = this->heapVec[this->currentSize];
		this->heapVec.pop_back();
		this->currentSize--;
		percDown(1);
		return ret;
	}

	bool isEmpty() {
		return this->currentSize == 0;
	}

	//返回堆中元素的个数
	int size() {
		return this->currentSize;
	}

	//根据一个vector容器创建堆
	void buildHeap(vector<int>& vec) {
		int i = vec.size() / 2; // 从树的中间开始，向根的方向操作，percDown方法保证了最大的节点总是沿着树向下移动
		this->currentSize = vec.size();
		this->heapVec = { 0 };
		for (auto iter = vec.begin(); iter != vec.end(); iter++) {
			this->heapVec.push_back(*iter);
		}
		while (i > 0) {
			percDown(i);
			i--;
		}
	}
	vector<int> heapVec;
	int currentSize;
};

//测试
void test01() {
	BinaryHeap hp;
	hp.insert(7);
	hp.insert(5);
	hp.insert(8);
	cout << hp.findMin() << endl;
	cout << hp.size() << endl;
	cout << hp.isEmpty() << endl;
	cout << hp.delMin() << endl;
	vector<int> myVec = { 9, 6, 5, 2, 3 };
	hp.buildHeap(myVec);
	cout << hp.findMin() << endl;
	cout << hp.size() << endl;
}

void main() {
	test01();
	system("pause");
}
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

4 最大堆的C++编程实现

最大堆和最小堆类似，按照其性质编写即可。

5 参考资料

《Python数据结构与算法分析》
《大话数据结构》