简单说明
优先队列可以根据key值的大小将元素进行排序、先被pop的通常是优先级最高的。
优先队列的内部实现其实是利用了堆的数据结构、binary heap是一种完全二叉树、以大堆为例、每棵树的根节点的key值一定大于其子孙节点的key值、完全二叉树处了最底层的叶子节点外、其他位置都是填满的。这样我们可以利用数组来存储所有节点。
若将数组从下标1开始存储元素、那么下标为 i 的节点的左孩子节点的下标为 2 * i、而右孩子节点下标为 2 * i 1;这样可以很容易定位一个节点的孩子节点或父节点的在数组中位置。
在heap内部维护一个数组vector用来保存元素、方便建立堆和节点的添加删除。
push_heap算法
1、添加元素，也就是需要将元素添加到最底层叶子节点从左向右的空位置上。就是vector的最后一个位置。
2、通过下标计算出新节点的父亲节点、与父节点key值比较、若比父节点大、则与父节点进行位置交换、不断上溯直到比父节点小或者父节点为空（也就是本身成为了根节点）。
3、在与父节点交换时、只需要交换他们的值就好。
pop_heap算法
1、因为是队列、每次pop是删除都是删除根节点。
2、由于要保证heap的complete binary tree结构、每次删除的节点实际上都是最后一块内存空间（vector中最后一个位置）。
3、删除根节点时需要比较左右节点的key值、与删除节点进行交换，然后以删除节点位置开始向下查找（重复）。
代码实现：
#pragma once
#include
#include
#include
using namespace std;
template
class priorityqueue
{
public:
explicit priorityqueue(function cmp):nodes(1,0),cmp(cmp){
}
~priorityqueue(){
destroy();
}
private:
void swap(int x, int y) {
auto p = nodes[x];
nodes[x] = nodes[y];
nodes[y] = p;
}
void destroy() {
for (priorityqueuenode* x : nodes) {
delete x;
}
nodes.clear();
}
public:
void push(t x) {
auto node = new priorityqueuenode(x);
nodes.push_back(node);
int index = nodes.size() - 1;
if (index == 1) //从1开始
return;
int parentindex = index / 2;
while (parentindex && cmp && cmp(nodes[index]->value,nodes[parentindex]->value)) {
swap(index, parentindex);
index = parentindex;
parentindex = index / 2;
}
}
const t& front() {
return nodes[1]->value;
}
void pop() {
int index = 1, leftindex, rightindex;
int endindex = nodes.size();
while (true) {
leftindex = index * 2;
rightindex = leftindex 1;
if (rightindex < endindex) {
if (cmp && cmp(nodes[leftindex]->value, nodes[rightindex]->value)) {
swap(leftindex, index);
index = leftindex;
}
else {
swap(rightindex, index);
index = rightindex;
}
}
else if (leftindex < endindex) {
swap(index, leftindex);
index = leftindex;
}
else {
break;
}
}
if (index != endindex - 1) {
swap(index, endindex - 1);
}
nodes.pop_back();
}
int qsize() {
return nodes.size() - 1;
}
private:
struct priorityqueuenode
{
t value;
priorityqueuenode(t val):value(val){}
};
vector nodes;
function cmp;
}; 总结：
优先队列的规则不是先进先出了、而是优先级高的排在前面、常常用建立大堆的方法解决在一个数组中查找最大的n个数的问题。堆排序的时间复杂度为nlogn。