优先队列
insert：向优先队列中插入新的元素
deleteMin：找出、返回并删除优先队列中最小的元素
实现工具：二叉堆
二叉堆
一颗被完全填满的二叉树，遵循『从上到下，从左到右』填入结点，即完全二叉树
表面上是一个二叉树，但是经过观察发现：
对于一个位置为 的结点，它的父结点是 ，左儿子结点是 ，右儿子结点是
注意：i是结点在堆中的位置，不是其关键字大小
根据位置特点，得到这样一个结论：可以由一个数组和一个代表当前堆大小的整数，组成表示二叉堆的结构
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
| template<class Comparable>
class BinaryHeap {
explicit BinaryHeap(int capacity = 100);
explicit BinaryHeap(const std::vector<Comparable> &items) : array(items.size() + 10), currentSize(items.size()) {
for (int i = 0; i < items.size(); ++i)
array[i + 1] = items[i];
buildHeap();
}
bool isEmpty() const { return currentSize == 0; }
const Comparable &findMin() const { return array[1]; }
void insert(const Comparable &x);
void insert(Comparable &&x);
void deleteMin();
void deleteMin(const Comparable &minItem);
void makeEmpty() {
while (currentSize)
deleteMin();
}
private:
int currentSize;
std::vector<Comparable> array;
void buildHeap() {
for (int i = currentSize / 2; i > 0; --i)
percolateDown(i);
}
void percolateDown(int hole);
};
|
堆序性质：使操作被快速执行的性质
将最小元设置在根结点上，每一个结点都大于父结点，小于儿子结点
左边的树是一个堆，右边的树不是（虚线表示堆的有序性被破坏）
创建二叉堆
获得一个无序数组，通过构建一个小根堆，得到一个逻辑上的升序序列
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
| template<class Comparable>
class BinaryHeap {
explicit BinaryHeap(const std::vector<Comparable> &items) : array(items.size() + 10), currentSize(items.size()) {
for (int i = 0; i < items.size(); ++i)
array[i + 1] = items[i];
buildHeap();
}
private:
int currentSize;
std::vector<Comparable> array;
void buildHeap() {
for (int i = currentSize / 2; i > 0; --i)
percolateDown(i);
}
void percolateDown(int hole);
};
template<class Comparable>
inline void
BinaryHeap<Comparable>::percolateDown(int hole) {
int child;
Comparable tmp = std::move(array[hole]);
for (; hole * 2 <= currentSize; hole = child) {
child = hole * 2;
if (child != currentSize && array[child + 1] < array[child])
++child;
if (array[child] < tmp)
array[hole] = std::move(array[child]);
else
break;
}
array[hole] = std::move(tmp);
}
|
重点关注percolateDown函数，通过这个函数中针对元素的下滤操作，构建一个小根堆
insert
保证堆结点的大小是从上到下，从左到右依次递增
在下一个空用位置创建一个空穴（hole），将待插入结点放入空穴
- 尝试在空穴 A 插入结点 14，发现作为儿子节点小于父结点，不合适
- 互换空穴 A 和结点 31 的位置
- 尝试在互换后的空穴 A 插入结点 14，发现作为儿子节点小于父结点，不合适
- 互换空穴 A 和结点 21 的位置
- 尝试在互换后的空穴 A 插入结点 14，发现合适，完成插入
上滤：新元素在队中上滤，直到找到正确的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| template<class Comparable>
inline void
BinaryHeap<Comparable>::insert(const Comparable &x) {
if (currentSize == array.size() - 1)
array.resize(array.size() * 2);
int hole = ++currentSize;
Comparable copy = x;
array[0] = std::move(copy);
for (; x < array[hole / 2]; hole /= 2)
array[hole] = std::move(array[hole / 2]);
array[hole] = std::move(array[0]);
}
|
deleteMin
直接根结点即最小元，然后通过类似于insert的上滤操作，将最后一个结点放置在合适的位置
- 删除最小元，结点 13，创建空穴 A；提取最后的结点 31
- 互换空穴 A 和结点 31 的位置，结点 31 大于儿子节点，不合适
- 互换空穴 A 和儿子节点中最小的结点 14
- 互换空穴 A 和结点 31 的位置，结点 31 大于儿子节点，不合适
- 互换空穴 A 和儿子节点中最小的结点 19
- ……
- 最终得到合适的位置，将结点 31 安置在适当位置
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
| template<class Comparable>
inline void
BinaryHeap<Comparable>::deleteMin() {
if (isEmpty())
throw UnderflowException();
array[1] = std::move(array[currentSize--]);
percolateDown(1);
}
template<class Comparable>
inline void
BinaryHeap<Comparable>::deleteMin(const Comparable &minItem) {
if (isEmpty())
throw UnderflowException();
minItem = std::move(array[1]);
array[1] = std::move(array[currentSize--]);
percolateDown(1);
}
template<class Comparable>
inline void
BinaryHeap<Comparable>::percolateDown(int hole) {
int child;
Comparable tmp = std::move(array[hole]);
for (; hole * 2 <= currentSize; hole = child) {
child = hole * 2;
if (child != currentSize && array[child + 1] < array[child])
++child;
if (array[child] < tmp)
array[hole] = std::move(array[child]);
else
break;
}
array[hole] = std::move(tmp);
}
|