如何实现一个最小堆
本文介绍如何使用 C++ 实现一个通用的、线程安全的最小堆
顺便一提，写此文的时候突然想到了多年以前（16、17年）盛行的 Mooc，当时国内有很多类似的慕课网站，也有很多优秀的课程，我的基础数据结构和算法就是一位 ACM 铜牌的老师教的，至今受用，但是现在好像很少看到此类网站了，还是比较可惜的。
进入正题，最小堆本身是一个完全二叉树，保证每一个节点都不会大于其左右子节点，要实现一个最小堆的两个核心函数是 sift_up 和 sift_down，用于调整最小堆结构以符合定义。
首先给出 MinHeap 的基本定义和成员变量：
1
2
3
4
5
6
| template <std::three_way_comparable T>
class MinHeap
{
std::shared_mutex mtx;
std::vector<T> vec;
};
|
这里 vec 用于保存最小堆的各个节点（完全二叉树很适合用数组保存），而 std::three_way_comparable 则是对容器元素类型的 concept 约束，要求元素类型必须是可比较的，毕竟不可比较的话也就没有“最小”的概念了。
sift_down 和 sift_up 是相反的一组用于调整堆的操作，sift_down 用于将一个元素向下调整至满足最小堆的条件，sift_up 则相反，由此可以知道对于任何一个完全二叉数我们只需要上到下执行 sift_down 或者从下到上执行 sift_up 就可以使得堆中的每一个节点都满足最小堆的条件
1
2
3
| 5 sift_down(5) 2
/ \ ==============> / \
2 6 sift_up(2) 5 6
|
可以看到不管是对 2 所在的节点执行 sift_up 还是对 5 所在的节点执行 sift_down 都能完成我们想要的效果。
接着在给出二者的定义前先给出对最小堆的一些基本操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public:
void push (T val)
{
std::unique_lock lock {mtx};
vec.push_back(val);
sift_up(vec.size()-1);
}
void pop()
{
assert(!vec.empty());
std::unique_lock lock {mtx};
vec[0] = vec.back();
vec.pop_back();
sift_down(0);
}
const T& top()
{
assert(!vec.empty());
std::shared_lock lock {mtx};
return vec.front();
}
|
push 和 pop 就是对堆调整以符合最小堆定义的过程，因为每次只有一个节点发生变化（新增或者删除），所以只需要对涉及的节点调整即可
下面给出 sift_up 和 sift_down 的定义如下：
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
| void sift_up(size_t index)
{
if (index == 0) return;
size_t parent = (index - 1) / 2;
if (vec[index] < vec[parent]) {
std::swap(vec[index], vec[parent]);
sift_up(parent);
}
}
void sift_down(size_t index)
{
if (index >= vec.size()) return;
size_t left = index * 2 + 1;
size_t right = index * 2 + 2;
std::optional<size_t> swap_to;
if (left < vec.size() && vec[left] < vec[index]) {
swap_to = left;
}
if (right < vec.size() && vec[right] < vec[index]) {
if (!swap_to || vec[right] < vec[swap_to.value()]) {
swap_to = right;
}
}
if (swap_to) {
std::swap(vec[index], vec[swap_to.value()]);
sift_down(swap_to.value());
}
}
|
应该还是比较好理解的，因为只有一个节点不（一定）满足最小堆条件，因此对于 sift_up 只需要判断自身和其父节点的大小关系并交换即可，而对于 sift_down 则是需要选出两个子节点中更小的那个并与之交换。
注意这里的 sift_up 和 sift_down 都是一个递归的过程，直到抵达堆的根节点或者叶子节点
以上我们就已经实现了一个通用的、线程安全的最小堆，这里给出堆的完整定义（为了方便使用包含 dump）：
完整的 MinHeap 实现
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
| template <std::three_way_comparable T>
class MinHeap
{
std::shared_mutex mtx;
std::vector<T> vec;
public:
void push (T val)
{
std::unique_lock lock {mtx};
vec.push_back(val);
sift_up(vec.size()-1);
}
void pop()
{
assert(!vec.empty());
std::unique_lock lock {mtx};
vec[0] = vec.back();
vec.pop_back();
sift_down(0);
}
const T& top()
{
assert(!vec.empty());
std::shared_lock lock {mtx};
return vec.front();
}
void sift_up(size_t index)
{
if (index == 0) return;
size_t parent = (index - 1) / 2;
if (vec[index] < vec[parent]) {
std::swap(vec[index], vec[parent]);
sift_up(parent);
}
}
void sift_down(size_t index)
{
if (index >= vec.size()) return;
size_t left = index * 2 + 1;
size_t right = index * 2 + 2;
std::optional<size_t> swap_to;
if (left < vec.size() && vec[left] < vec[index]) {
swap_to = left;
}
if (right < vec.size() && vec[right] < vec[index]) {
if (!swap_to || vec[right] < vec[swap_to.value()]) {
swap_to = right;
}
}
if (swap_to) {
std::swap(vec[index], vec[swap_to.value()]);
sift_down(swap_to.value());
}
}
void dump()
{
std::shared_lock lock {mtx};
for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
std::cout << *iter;
if (std::distance(iter, vec.end()) != 1) {
std::cout << ", ";
} else {
std::cout << std::endl;
}
}
}
};
|
用法示例以及运行结果如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| auto main(void) -> int {
auto heap = MinHeap<int> {};
heap.push(177);
heap.push(3);
heap.push(110);
heap.push(19);
heap.pop();
heap.push(21);
heap.push(112);
heap.push(18);
std::cout << "heap's top is " << heap.top() << std::endl;
heap.dump();
heap.pop();
heap.pop();
std::cout << "heap's top is " << heap.top() << std::endl;
heap.dump();
return 0;
}
|
运行结果：
1
2
3
4
| heap's top is 18
18, 21, 19, 177, 112, 110
heap's top is 21
21, 112, 110, 177
|
可以看到不论我们以任何顺序插入和删除元素都能够保证 MinHeap 始终是一个最小堆