优先队列
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); }
|