优先队列是一种常用的ADT，其中的元素有序排列，入队的元素会插入到正确的位置，队首元素始终为最小(大)值，队首出队后优先队列仍然保持原来的性质。
这里我们规定优先队列以升序排列。
优先队列提供的接口包括：
- insert 插入元素
- top 得到队首元素
- pop 删除队首元素
二叉堆是优先队列一种常用的实现，二叉堆是一种完全二叉树，完全二叉树除最低一层外其它层均被填满，最低一层的节点全部集中在左侧。完全二叉树的性质决定它可以很容易地由二叉数组来实现。
二叉堆满足堆序性，即任意一个节点X的父节点不大于X(最小堆)。由堆序性可知，二叉堆的根节点一定为最小值或最大值，根节点为最小值的堆称为最小堆，根节点为最大值的堆称为最大堆。
最小堆类的声明：
template<typename val_t>
class MinHeap {
protected:
const static size_t capcity = 10000;
size_t size;
val_t vec[capcity];
public:
MinHeap();
void insert(val_t val);
bool empty();
void rmMin();
val_t getMin() {
return vec[1];
};
~MinHeap() = default;
};
插入元素
插入元素采用上滤的方法:
(1)在数组超出末端(size位置)创建一个空穴
(2)比较新元素与空穴父节点的大小，若新元素较大则将原父节点填入空穴，原父节点的位置变为空穴
(3)直至新元素不大于空穴父节点时停止空穴上溯
template<typename val_t>
void MinHeap<val_t>::insert(val_t val) {
size_t i;
for (i = ++size; vec[i/2] > val; i /= 2) {
vec[i] = vec[i / 2];
}
vec[i] = val;
}
在实现过程中，我们只是用i标记了空穴的位置，并没有交换空穴与父节点的位置。
删除根元素
删除元素采用恰好相反的下滤策略:
(1) 移除根节点后在根节点处产生了一个空穴
(2) 比较空穴的左右子节点，较大的一个与空穴交换位置，直至空穴到达最下层
(3) 将原来最后一个元素填入空穴的位置
template<typename val_t>
void MinHeap<val_t>::rmMin() {
size_t i, next;
val_t min, last;
if (empty()) {
return;
}
min = vec[1];
last = vec[size--];
for (i = 1; i * 2 <= size; i = next) {
//find smaller next
next = i * 2;
if (next != size && vec[next + 1] < vec[next]) {
next++;
}
//
if (last > vec[next]) {
vec[i] = vec[next];
}
else {
break;
}
}
vec[i] = last;
}
一言不发就丢代码：
#include <iostream>
//#include <vector>
using namespace std;
template<typename val_t>
class MinHeap {
protected:
const static size_t capcity = 10000;
size_t size;
val_t vec[capcity];
public:
MinHeap();
void insert(val_t val);
bool empty();
void rmMin();
val_t getMin() {
return vec[1];
};
~MinHeap() = default;
};
template<typename val_t>
MinHeap<val_t>::MinHeap() {
size = 0;
}
template<typename val_t>
bool MinHeap<val_t>::empty() {
if (size) {
return false;
}
else {
return true;
}
}
template<typename val_t>
void MinHeap<val_t>::insert(val_t val) {
size_t i;
for (i = ++size; vec[i/2] > val; i /= 2) { //covert > to <, to get a max heap
vec[i] = vec[i / 2];
}
vec[i] = val;
}
template<typename val_t>
void MinHeap<val_t>::rmMin() {
size_t i, next;
val_t min, last;
if (empty()) {
return;
}
min = vec[1];
last = vec[size--];
for (i = 1; i * 2 <= size; i = next) {
//find smaller next
next = i * 2;
if (next != size && vec[next + 1] < vec[next]) {
next++;
}
//
if (last > vec[next]) {
vec[i] = vec[next];
}
else {
break;
}
}
vec[i] = last;
}