1. 二叉堆
1.1 二叉堆的定义
二叉堆在逻辑上是一颗完全二叉树，而在存储方式上还是用数组进行存储的。二叉堆具有如下性质，如果当前节点在数组中的索引为 ，那么有：
- 其左子节点在数组中的索引为 \(2i+1\);
- 其右子节点在数组中的索引为 \(2i+2\);
- 其父节点在数组中的索引为 \((i-1)/2\);
二叉堆的结构如下图所示：
常见的二叉堆有两种形式，分别是【大根堆】和【小根堆】，其中前者的堆顶是整个序列中最大的元素，后者的堆顶则是整个序列中最小的元素。如果下标 i 满足 \(0\leq i\leq (n-1)/2\)，其中 n 表示最后一个元素的下标，那么可以通过如下方法来判断当前序列为大根堆还是小根堆：
- 大根堆：满足 arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]
- 小根堆：满足 arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]
大根堆和小根堆如下图所示：
1.2 二叉堆的操作
二叉堆的操作分为入堆和出堆。入堆或者出堆后需要重新调整堆的结构，使其满足大根堆或者小根堆的条件，这个操作的过程分为【上浮】和【下沉】。
1.2.1 上浮
如图所示，为大根堆入堆后的上浮操作过程，先将入堆元素添加在数组末尾位置，然后与其父节点进行比较。对于大根堆而言，如果大于父节点，则与父节点交换位置；对于小根堆而言，如果小于父节点，则与父节点交换位置，重复上述操作，直到满足大根堆/小根堆的条件：
1.2.2 下沉
如图所示，为大根堆出堆时的下沉操作过程，先将堆顶元素出堆，然后将数组最末尾位置的元素放入到堆顶位置，与其左、右子节点进行比较。对于大根堆而言，找出值最大的子节点并与其交换位置；对于小根堆而言，找出值最小的子节点并与其交换位置，重复上述操作，直到其满足大根堆/小根堆的条件：
综上所述，无论是上浮操作还是下沉操作，其时间复杂度均为 \(O(logn)\)，空间复杂度均为 \(O(1)\)。
1.3 优先级队列的实现
优先级队列的代码实现如下，可以通过传入不同的函数对象来创建大根堆/小根堆，当传入的函数对象为 greater<int>() 时为大根堆，为 less<int>() 时为小根堆：
class PriorityQueue {
public:
using Comp = function<bool(int, int)>;
PriorityQueue(int cap = 20, Comp comp = greater<int>());
~PriorityQueue();
// 入堆
void push(int val);
// 出堆
void pop();
// 获取堆顶元素
int top() const;
// 堆大小
int size() const;
// 堆是否为空
bool empty() const;
// 打印堆
void print() const;
private:
// 上浮操作
void siftUp(int idx, int val);
// 下沉操作
void siftDown(int idx, int val);
// 数组扩容
void expand(int size);
private:
int* que_; // 动态扩容的数组
int size_; // 数组元素的个数
int cap_; // 数组的总空间大小
Comp comp_; // 比较器对象
};
PriorityQueue::PriorityQueue(int cap, Comp comp)
: que_(new int[cap])
, size_(0)
, cap_(cap)
, comp_(comp) {
}
PriorityQueue::~PriorityQueue() {
delete[] que_;
que_ = nullptr;
}
void PriorityQueue::push(int val) {
if (size_ == cap_) expand(cap_ * 2);
if (size_ == 0) {
que_[size_] = val;
} else {
siftUp(size_, val);
}
size_++;
}
void PriorityQueue::pop() {
if (size_ == 0)
throw "priority queue is empty";
size_--;
if (size_ != 0) {
siftDown(0, que_[size_]);
}
}
int PriorityQueue::top() const {
if (size_ == 0)
throw "priority queue is empty";
return que_[0];
}
int PriorityQueue::size() const {
return size_;
}
bool PriorityQueue::empty() const {
return size_ == 0;
}
void PriorityQueue::print() const {
for (int i = 0; i < size_; i++) {
cout << que_[i] << " ";
}
cout << endl;
}
void PriorityQueue::siftUp(int idx, int val) {
while (idx > 0) {
int father = (idx - 1) / 2;
if (comp_(val, que_[father])) {
que_[idx] = que_[father];
idx = father;
} else {
break;
}
}
que_[idx] = val;
}
void PriorityQueue::siftDown(int idx, int val) {
// 下沉时不能超过最后一个有孩子的节点
while (idx < size_ / 2) {
int child = 2 * idx + 1;
if (child + 1 < size_ && comp_(que_[child + 1], que_[child])) {
// 有右孩子 且右孩子的值大于左孩子 则将其更新为右孩子
child++;
}
if (comp_(que_[child], val)) {
que_[idx] = que_[child];
idx = child;
} else {
break;
}
}
que_[idx] = val;
}
void PriorityQueue::expand(int size) {
int* p = new int[size];
memcpy(p, que_, cap_ * sizeof(int));
delete[] que_;
que_ = p;
cap_ = size;
}
2. STL实现
2.1 heap
heap 并不属于 STL 的容器组件，它是 priority queue 的底层容器，实现了二叉堆数据结构。priority queue 允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先级最高的元素开始取，因此称作【优先级队列】。
heap 的实现是通过一个完全二叉树，即整棵二叉树除了最底层的叶节点之外，是填满的，而最底层的叶节点由左至右又不得有空隙。
SGI STL 中将此数组以 vector 来代替。根据元素排列方式，heap 可以分为【max-heap(大根堆)】和【min-heap(小根堆)】两种，前者每个节点的键值都大于或等于其子节点键值，后者的每个节点键值都小于或等于其子节点键值。因此，前者的最大值在根节点，并位于数组的起始处，而后者的最小值在根节点，并位于数组的起始处。STL 提供的是 max-heap。
heap 所有元素都必须遵循特别的完全二叉树排列规则，所以 heap 不提供遍历功能，也不提供迭代器。
2.2 priority queue
priority queue 是一个拥有权值观念的 queue，它允许加入新元素，移除旧元素，审视元素值等功能。由于这是一个 queue，所以只允许在底端加入元素，并从顶端取出元素，除此之外别无其他存取元素的途径。
priority queue 带有权值观念，其内的元素并非按照被推入的次序排列，而是自动依照元素的权值排列。权值最高者，排在最前面。
缺省情况下，priority queue 利用一个 max-heap 完成。
注意：pop() 并不是真的将元素弹出，而是重排 heap，然后再以底层容器的 pop_back() 取得被弹出的元素。priority queue 不提供遍历功能，也不提供迭代器。