STLC++STLSTL-priority-queue优先级队列
HappyLadySaucepriority_queue 优先级队列
堆的概念
STL中的 priority_queue 是数据结构中的堆，堆的本质是一个完全二叉树，而堆又分为大根堆和小根堆。
- 小根堆（min heap）：任意节点的值 ≤ 其子节点的值。
- 大根堆（max heap）：任意节点的值 ≥ 其子节点的值。
我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。不难发现，对于大顶堆（小顶堆），堆顶元素（根节点）的值总是最大（最小）的。
堆的存储结构
堆是一个非线性的树形结构，但是在计算机实现当中，我们往往是采用数组的形式进行存储。
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
在这一段数组中，我们使用公式来判断一个节点的子节点和父节点。
堆节点公式
给定索引 i ，其左子节点的索引为 2 i + 1 ，右子节点的索引为 2 i + 2 ，父节点的索引为 ( i − 1 ) / 2 （向下整除）。当索引越界时，表示空节点或节点不存在。
如何建堆
给定一个数组，我们要如何才能实现堆的逻辑结构呢？这涉及到建堆操作，堆分为大根堆和小根堆的，堆总是有序的。其实建堆就是把数组中的数据按照堆的逻辑结构（完全二叉树）进行大小排序，就可以完成建堆操作。
那么我们怎样才能实现按照堆的逻辑结构进行排序呢？首先堆是分为大小根堆的，STL 中默认为大根堆，那么我们首先实现大根堆排序建堆。
大根堆是根节点最大，叶子节点最小的排序方式。按照常规排序思想，我们首先从最后一个叶子节点开始排序。
向上调整建堆
在这里我们会遇到一个问题，该怎样进行排序？大根堆最基本的逻辑就是父亲节点的值总是大于子节点的值，所以我们首先比较左右子节点值的大小，比较得出是左子树的值大还是右子树的值大，然后再使用较大的子节点值与父亲节点值进行比较，如果子节点值小于父亲节点值，则不进行任何操作这已经满足堆的逻辑，反之进行值替换，接着将子节点重新赋值为父亲节点，再重新计算父亲节点进入下一轮值比较，直至达到根节点或者子节点值小于父亲节点值时，停止排序。
这是向上调整建堆的思路，但是这个思路有一个致命问题：向上调整是从叶子节点开始，每次只调整一个元素，导致最坏情况下，向上排序建堆的时间复杂度为 $O(nlogn)$ 。
向下调整建堆
向下调整的核心思想是从下到上依次调整一个子树。
向下调整思想将数据分为多个子树，每个子树只需向下调整好自己的子树，保证自己一定是一个大根堆，从后往前依次调整（子树 1 -> 子树 2 -> 子树 3），自然地最终我们的堆就排好序了。最终向下调整算法的时间复杂度为 $O(n)$ 。
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
| template<class T, class Container = vector<T>>
class priority_queue
{
private:
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while(child > 0 && _con[child] > _con[parent])
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
}
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < _con.size())
{
int max_value = child + 1 < _con.size() && _con[child] < _con[child + 1] ? child + 1 : child;
if (_con[parent] < _con[max_value])
{
std::swap(_con[parent], _con[max_value]);
parent = max_value;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
public:
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
for (int i = (_con.size() - 1 -1) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
private:
Container _con;
}
|
STL priority_queue 实现
STL 中堆的实现并不复杂，它和 queue、stack 一样采用了容器适配器的设计，默认容器设置为 vector 。因为 vector 非常适合作为 priority_queue 的底层容器，至于为什么前面已经讨论过原因了。
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
|
template<class T, class Container = vector<T>>
class priority_queue
{
private:
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < _con.size())
{
int max_value = child + 1 < _con.size() && _con[child] < _con[child + 1] ? child + 1 : child;
if (_con[parent] < _con[max_value])
{
std::swap(_con[parent], _con[max_value]);
parent = max_value;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while(child > 0 && _con[child] > _con[parent])
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
}
public:
typedef typename Container::iterator iterator;
typedef typename Container::const_iterator const_iterator;
iterator begin()
{
return _con.begin();
}
iterator end()
{
return _con.end();
}
priority_queue()
{
}
~priority_queue()
{
clear();
}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
for (int i = (_con.size() - 1 -1) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
void push(const T& value)
{
_con.push_back(value);
AdjustUp(_con.size() - 1);
}
T top() const
{
return _con[0];
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
void clear()
{
_con.clear();
}
void swap(priority_queue& other)
{
std::swap(_con, other._con);
}
private:
Container _con;
};
|
