c++实现最大堆

前言

在写leetcode的时候，看到一道优先队列的题目，复习了一下最大堆，用c++实现了一下。以前听网课的时候，根本看不懂实现，现在自己也能实现了。

参考文献

这个我觉得讲得挺好的，图很生动形象

代码

#include
#include

class MaxHeap {
public:
	MaxHeap(std::vector<int>& nums); // 用一个数组建立最大堆

	int top(); // 取出堆顶元素
	void pop(); // 删除堆顶元素

	void insert(int num); // 插入元素

	void print()
	{
		for (int i = 1; i < this->_nums.size(); ++i)
		{
			std::cout << this->_nums[i] << " ";
		}
		std::cout << std::endl;
	}

private:
	std::vector<int> _nums; // 最大堆数组
};


int main()
{
	std::vector<int> nums2;
	MaxHeap b(nums2);  测试异常

	// 正常情况
	std::vector<int> nums{ 1,2,3,4,5 };
	MaxHeap aHeap(nums);
	aHeap.print();

	//std::cout << aHeap.top() << std::endl;

	aHeap.pop();
	aHeap.print();

	aHeap.insert(6);
	aHeap.print();

	return 0;
}

MaxHeap::MaxHeap(std::vector<int>& nums)
{
	int cnt = nums.size();
	if (cnt < 1)
	{
		std::cout << "vector param must has at least one element." << std::endl;
		return;
	}

	this->_nums.assign(cnt + 1, 0); // 开辟cnt+1个空间

	for (int i = 1; i <= cnt; ++i)
	{
		this->_nums[i] = nums[i-1];

		// 和它的父节点比较
		int father_index = i / 2;
		int cur_position = i; // 它的当前位置
		while (father_index > 0) // 一直交换到它小于它的父节点
		{
			if (this->_nums[cur_position] > this->_nums[father_index])
			{
				// 交换
				int tmp = this->_nums[father_index];
				this->_nums[father_index] = this->_nums[cur_position];
				this->_nums[cur_position] = tmp;

				cur_position = father_index; // 更新它的当前位置
				father_index /= 2; // 更新父节点
			}
			else break;
		}
	}			
}

int MaxHeap::top()
{
	if (this->_nums.size() == 0) {
		std::cout << "heap's size == 0, unleagal operation." << std::endl;
		return 0;
	}
	return this->_nums[1];
}

void MaxHeap::pop()
{
	if (this->_nums.size() == 0) {
		std::cout << "heap's size == 0, unleagal operation." << std::endl;
		return;
	}

	// 堆顶元素移除, 重新恢复最大堆
	// 将最后一个元素放到堆顶
	int size = this->_nums.size();
	this->_nums[1] = this->_nums[size - 1];
	size = size - 1;
	this->_nums.resize(size);

	int cur_position = 1; // 记录当前位置
	int son_max_value; // 孩子的最大值

	while (cur_position < size - 1) 
	{
		if (cur_position * 2 <= size - 1)
		{
			int son_max_value_index = cur_position * 2;
			// 左孩子存在
			son_max_value = this->_nums[cur_position * 2];

			if (cur_position * 2 + 1 < size - 1)
			{
				// 右孩子存在
				son_max_value = son_max_value > this->_nums[cur_position * 2 + 1] ? son_max_value : this->_nums[cur_position * 2 + 1];
				if (son_max_value == this->_nums[cur_position * 2 + 1])
				{
					son_max_value_index += 1;
				}
			}
			//std::cout << cur_position << std::endl;

			if (this->_nums[cur_position] < son_max_value)
			{
				// 交换
				int tmp = this->_nums[son_max_value_index];
				this->_nums[son_max_value_index] = this->_nums[cur_position];
				this->_nums[cur_position] = tmp;

				cur_position = son_max_value_index;
			}
			else {
				//std::cout << cur_position << std::endl;
				break;
			}
		}
		else break;
	}
}

void MaxHeap::insert(int num)
{
	if (this->_nums.size() == 0) {
		std::cout << "heap's size == 0, unleagal operation." << std::endl;
		return;
	}

	// 在最后面插入元素
	this->_nums.push_back(num);
	// 然后将它调成最大堆

	int cur_position = this->_nums.size()-1;
	int father_index = cur_position / 2;
	int father_index_value;

	while (father_index > 0) // 只要没有到堆顶就有一直比较的可能
	{
		father_index_value = this->_nums[father_index];
		if (father_index_value < num) {
			// 交换			
			this->_nums[father_index] = num;
			this->_nums[cur_position] = father_index_value;

			cur_position = father_index;
			father_index = cur_position / 2;
		}
		else break;
	}
}

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
175