堆又称为优先队列，其通常包括至少两种操作：入队操作和出队操作。
普通队列与优先队列
普通队列：先进先出，后进后出
优先队列：出队序列和入对序列无关，只与优先级有关
为什么选择优先队列？
动态的选择优先级最高的任务执行
在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．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
网友评论