堆和优先队列

堆又称为优先队列，其通常包括至少两种操作：入队操作和出队操作。

普通队列与优先队列

普通队列：先进先出，后进后出
优先队列：出队序列和入对序列无关，只与优先级有关

---

为什么选择优先队列？

动态的选择优先级最高的任务执行
在N个元素中选出前M个元素
排序的时间复杂度为O(NlogN)
使用优先队列时间复杂度为O(NlogM)
当N的较大，M较小的时候，使用优先队列比较快

优先队列的实现

类型	入队	出队
普通数组	O(1)	O(n)
顺序数组	O(n)	O(1)
堆	O(lgn)	O(lgn)

采用普通数组，依次入队，选择出队
顺序数组，排列入队
堆，平衡入队与出队的时间，使其保持在O(lgn)
采用普通数组，最差的情况为O(n^2)

完全二叉树

叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

二叉堆

二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

二叉堆满足二个特性：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。