优先队列
对于排序，比如快排等将一个序列排成有序，其中包含最大、最小值。但是有时候我们并不需要知道整个序列的排序情况，只想知道最值，这个最值可能是最大、最小值。这时我们就可以使用优先队列。
优先队列应用
- 调度： 选择优先级最高的进行调度
- 极值： 只想知道某些样本的极值
- 很多贪心算法中
- 堆排序
优先队列性质
本文介绍基于完全二叉树实现的优先队列
基于完全二叉树实现的优先队列性质
任何一颗子树的根节点都比它的两个子节点大/小
什么叫完全二叉树 ?
叶子节点只能出现在最底部的两层，且最底层叶节点均处于次底层叶节点的左侧。
完全二叉树可以用向量表示:
- 2*k+1为左孩子
- 2*k+2为右孩子
- k元素的父元素为k/2
- 根节点从0开始
上述性质可以使得我们使用vector数组来保存完全二叉树数据。
- v[0] 为根节点
- v[1] 为左孩子
- v[2] 为右孩子
完全二叉树高度： logN，没下一层，元素数量增加一倍，高度相对减半
依次类推
大顶堆
任务一颗子树的根节点元素都比它的两个子树节点元素值大，特别的，根元素(堆顶)为最大。
小顶堆
任务一颗子树的根节点元素都比它的两个子树节点元素值小，特别的，根元素(堆顶)为最小。
大小顶堆只是比较的时候是使用‘<’符号还是‘>’符号的问题，所以搞定一个，另一个换个符号即可。
优先队列API
// 优先队列基类
template <typename Key>
class PQ {
public:
PQ();
virtual ~PQ() = default;
void insert(Key v); // 插入一个元素
Key top(); // 返回顶部元素
Key delTop(); // 删除并返回顶部最大/最小元素
bool empty() { return _a.empty(); }
int size() { return _a.size()-1; }
protected:
virtual bool compare(int i, int j) = 0;
virtual void exch(int i, int j) = 0; // 交互i、j两个位置所在的元素
vector<Key> _a; // 从1开始,0位置不用
void sink(int k); // 顶部删除，尾部元素放在顶部下沉
void swim(int k); // 从尾部添加元素上浮
}; 关键操作插入和删除
维护优先队列的两个基本操作分别是插入insert、删除delTop。 底层涉及的操作分别对应为swim和sink。
插入上浮swim
优先队列插入一个数据在尾部k插入，然后通过比较父元素k/2进行上浮，不断重复与父元素比较，直到到达顶部元素。
插入时间复杂度
尾部插入后需要逐层与其父元素比较，直到顶部根元素，而完全二叉树的高度为logN，所以最多比较logN次，时间复杂度也就是logN。
// k位置元素与他的父元素比较，比父元素大/小上浮，直到父元素更大/更小或到达顶部
template <typename Key>
void PQ<Key>::swim(int k) {
while(k/2 >= 1 && compare(k, k/2)) {
exch(k/2, k);
k = k/2;
}
} 顶部删除下沉sink
优先队列从删除顶部元素，然后拿尾部的元素来填补顶部的空位。为了保持优先队列性质，需要从顶部元素依次与子节点元素比较，逐步下沉比较，直到叶子节点。
删除操作时间复杂度
从顶部删除，然后置换尾元素进行下沉比较，每次先比较两个子元素大小，然后再比较子元素较大的那个与下沉元素比较，所以确定一次下沉操作涉及两次比较，而最多下沉树高次，完全二叉树树高为logN，所以删除操作时间复杂度为2*logN。
// 下沉k索引所在的元素
// 在2k和2k+1两个子元素中比较那个大/小，与k进行交换
// 一直到没有子元素比k大/小，或者到达底部
template <typename Key>
void IndexPQ<Key>::sink(int k) {
int N = size(); // ！！！注意第一个元素没用
while(2*k <= N) {
int switch_child;
if(2*k < N ) {
// 满二叉树
switch_child = compare(2*k , 2*k+1) ? 2*k : 2*k+1; //2k和2k+1中较大/较小的那个索引
}
else {
// 差一个满树
switch_child = 2*k;
}
if(compare(switch_child, k)) {
exch(k, switch_child);
//交互之后原来k位置的元素到了switch_index索引位置，需要继续看下面子树是否需要继续下沉
k = switch_child;
}
else {
break;
}
}
} 索引优先队列
有时需要将插入元素与一个索引关联起来，比如合并三个有序超大数据流s1, s2, s3。它们每个流中数据都是有序的，流可能来自网络、文件、或者其他程序处理，现在需要合并这3个有序流。因为它们大到内存放不下，所以不能直接合并，这时可以使用索引优先队列进行有序合并，类似选择排序。
测试用例
SECTION("索引优先队列 : 合并三个有序流的数据") {
deque<char> v1({'A','B', 'C', 'F', 'G', 'I', 'I', 'Z'});
deque<char> v2({'B', 'D', 'H', 'P', 'Q', 'Q'});
deque<char> v3({'A', 'B', 'E', 'F', 'J', 'N'});
deque<deque<char>> vs = {v1, v2, v3};
deque<char> res;
res.insert(res.end(), v1.begin(), v1.end());
res.insert(res.end(), v2.begin(), v2.end());
res.insert(res.end(), v3.begin(), v3.end());
sort(res.begin(), res.end());
IndexPQ<char> *idxPQ = new MinIndexPQ<char>(3);
for(size_t i = 0; i < vs.size(); i++) {
if(!vs[i].empty()) {
idxPQ->insert(i, vs[i][0]);
vs[i].pop_front();
}
}
int cnt = 0;
while(!idxPQ->empty()) {
REQUIRE(res[cnt++] == idxPQ->top());
int i = idxPQ->delTop();
if(!vs[i].empty()) {
idxPQ->insert(i, vs[i][0]);
vs[i].pop_front();
}
}
} 索引优先队列实现API
// 索引优先队列
// 将一个索引与元素关联起来
template <typename Key>
class IndexPQ{
public:
IndexPQ(int max);
virtual ~IndexPQ() = default;
void insert(int index, Key v);
size_t size() { return N;}
bool empty() { return N==0;}
Key top(); // 隐藏基类方法
int delTop(); // 隐藏基类方法
protected:
size_t N; // 索引优先队列中有多少元素
vector<int> pq; // 二叉堆 从1开始
vector<int> qp;
vector<Key> keys; // 实际元素
virtual bool compare(int i, int j) = 0;
void sink(int k); // 顶部删除，尾部元素放在顶部下沉
void swim(int k); // 从尾部添加元素上浮
void exch(int i, int j){
swap(pq[i], pq[j]);
}
}; 同样，索引优先队列也可以分为索引小顶堆和索引大顶堆
索引小顶堆
// 索引小顶堆
template <typename Key>
class MinIndexPQ : public IndexPQ<Key> {
public:
MinIndexPQ(int max) : IndexPQ<Key>(max) {};
private:
bool compare(int i, int j) override {
return this->keys[this->pq[i]] < this->keys[this->pq[j]];
}
}; 索引大顶堆
// 索引大顶推
template <typename Key>
class MaxIndexPQ : public IndexPQ<Key> {
public:
MaxIndexPQ(int max) : IndexPQ<Key>(max) {};
private:
bool compare(int i, int j) override {
return this->keys[this->pq[i]] > this->keys[this->pq[j]];
}
}; 堆排序
我们还可以利用堆的性质构建一个排序算法，称作堆排序
堆排序的两个关键步骤
- 建堆
- 从堆顶选择最值交换到尾部，重新维护堆
关键思路： 从最后一个非叶子节点子树开始建堆 ！！！
对于上图就是j这个最后非叶子节点作为子树根所在的子树进行建堆。然后依次往回、往上建更大的堆，最终完成整个堆的构建。
这样，一下就省略了一半的元素，大大提高了建堆的效率。
为什么不是从叶子节点开始？
因为叶子节点只有一个元素，本身就是一个合法堆。
template <typename T>
void heap_sort(vector<T> &a, Compare<T> *compare) {
// 建堆
int N = a.size();
int k = N/2 - 1; // 第一个非叶子节点
while(k>=0) { // 还未超出根节点
sink(a, k, N, compare); // 从k位置作为子树根节点构建大顶堆/小顶堆
k--; // 上一个节点继续构建堆
}
// 每次去顶部最大值放到最后排序
while(N > 1) { // N == 1时就剩一个，不用排了
swap(a[0], a[--N]);
sink(a, 0, N, compare);
}
} 
京公网安备 11010502036488号