优先队列
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。
在优先队列中，元素被赋予优先级。删除元素时，具有最高优先级的元素最先删除。具有最高级先出队 （first in, largest out）的行为特征。
而堆是优先队列的一种很好实现。假设我们维护一个堆，而每次都把最高优先级的元素保持在堆顶，每次删除元素直接取堆顶元素。而在插入元素和删除元素之后，我们再重新调整，维护堆的特性。
插入元素
现在假设我们已经有个优先队列（值越大，优先级越高）。
优先队列.jpg
-
percolate up（上溯算法）
现在插入50
插入元素.jpg
如图所示：先直接把元素插在最末尾处，然后再执行一个percolate up（上溯）算法：将新结点拿来与父结点比较，如果其键值比父结点大，就与父结点对换位置。如此一直上溯，直到不需要对换或上溯到根节点为止。
删除最高优先级元素
-
percolate down（下溯算法）
删除最高优先级元素.jpg
如图所示：为了删除元素，先将堆顶结点和最后一个结点交换，然后删除最后一个元素(原堆顶元素)。此时堆的特性已经不满足，再从堆顶元素开始，执行一个下溯算法：找出当前结点的儿子结点中优先级较高的儿子结点，和当前结点优先级进行比较，如果当前结点优先级较低，与优先级较高的儿子结点交换，否则，则已经满足堆的特性，调整结束。按照此过程持续下放，直到调整到最后一棵子树。
代码
#define PARENT(index) ((index - 1) / 2)
#define LEFTCHILD(index) (index * 2 + 1)
#define RIGHTCHILD(index) (index * 2 + 2)
template<typename Key>
class PriorityQueue
{
public:
PriorityQueue() = default;
size_t size() const { return keys.size(); }
bool empty() const { return keys.size() == 0; }
void push(const Key &key);
void pop();
Key top()
{
assert(keys.size() != 0);
return keys[0];
}
private:
void percolateUp(int index); /* 上溯算法 */
void percolateDown(int index); /* 下溯算法 */
private:
std::vector<Key> keys;
};
template <typename Key>
void PriorityQueue<Key>::push(const Key &key)
{
keys.push_back(key);
percolateUp(keys.size()-1);
}
template <typename Key>
void PriorityQueue<Key>::pop()
{
if (keys.size() != 0)
{
std::swap(keys[0], keys[keys.size() - 1]);
keys.pop_back();
if (keys.size() > 0)
percolateDown(0);
}
}
/*
* 上溯算法：
* 将新结点拿来与父结点比较，如果其优先级比父结点高，就与父结点对换位置。
* 如此一直上溯，直到不需要对换或上溯到根节点为止。
*/
template<typename Key>
void PriorityQueue<Key>::percolateUp(int index)
{
assert((index >= 0 && index < keys.size()));
/* 当尚未到达顶端,且当前结点优先级比父结点高,就与父结点交换. */
int parentIndex = PARENT(index); // 找出父结点:(index - 1) / 2;
while (index > 0 && keys[index] > keys[parentIndex])
{
std::swap(keys[index], keys[parentIndex]);
percolateUp(parentIndex);
}
}
/* 下溯算法 */
template<typename Key>
void PriorityQueue<Key>::percolateDown(int index)
{
assert((index >= 0 && index < keys.size()));
if (keys.size() <= 1) // 没有结点和1个结点不需调整
return;
int lastNotLeave = static_cast<int>((keys.size()-1) -1) / 2; // 最后一个非叶子结点
int left = LEFTCHILD(index); // 当前结点的左儿子
int right = RIGHTCHILD(index); // 当前结点的右儿子
if (index <= lastNotLeave)
{
/* 找出当前结点的左右儿子结点中优先级较高的结点 */
int maxKeyIndex;
if (right <= keys.size() - 1)
maxKeyIndex = keys[left] >= keys[right] ? left : right;
else
maxKeyIndex = left;
if (keys[maxKeyIndex] > keys[index])
{
std::swap(keys[maxKeyIndex], keys[index]);
if (maxKeyIndex <= lastNotLeave)
percolateDown(maxKeyIndex);
}
}
}
