优先队列 priority queue

1.优先队列概念

优先队列（priority queue）是一种特殊的数据结构。
队列中每一个元素都被分配到一个优先权值，出队顺序按照优先权值来划分。
一般有两种出队顺序：高优先权出队或低优先权出队。
priority queue至少要有两个最基本的ADT：进队，出队（按照高优先权或低优先权）

产生原因：同样是为了提高数据处理的效率。试想，要实现优先队列对应的功能，若使用链表或者数组，那么要么先排序再插入，要么先插入再查找最大最小元素。这样一来，入队出队的时间复杂度至少为O(N)。

• 优先队列出队和入队的时间复杂度均为O(log N)。
• 优先队列基于二叉堆实现。

2.二叉堆（Heap）

堆是一种特殊的二叉树，性质如下：

• 每个结点的值都大于或等于其左右孩子结点的值（大顶堆），或每个结点的值都小宇或等于其左右孩子的值（小顶堆）。
• 必须满足完全二叉树的结构。

完全二叉树和满二叉树

完全二叉树 complete binary tree

叶节点只可能出现在最后两层，且最后一层的叶节点都左对齐
一棵深度为h的完全二叉树

满二叉树 full binary tree

深度为h的满二叉树有（2^h）-1个结点

由二叉堆的定义可以看出，跟结点一定是二叉堆中结点值最大（或最小）的。较大（或较小）的结点靠近根节点

堆的存储结构：

一般情况下，堆用数组来存储，第i个结点的父节点的下标就是（i-1）/2.
如果用层序遍历顺序将大顶堆和小顶堆存入数组，

则关系如图：

堆的重要操作

插入：插入一个元素之后，新元素首先被插入表层（即最后一层尽可能左边的位置），之后再根据堆的性质进行调整。

例：写出一次一个地将10,12,1,14,6,5,8,15,3,9,7,4,11,13和2插入一个初始为空的二叉堆的结果

删除：删除总是发生在根处，之后将最后一个元素（即最后一层最右边的元素）拿来填补空缺，之后根据堆的性质进行调整堆的结构。