优先队列

个人博客:www.zhouximin.com
模型
优先队列 主要有 2 个方法
deleteMin（）的工作就是 找出，返回并删除优先队列中最小的元素
insert（）的工作就是入队 等价于 enqueue（）
一开始我觉得 很简单啊 用数 或者 加入的时候 先排序 后来一思考。。这样 时间复杂度有点大了。然后继续看了书 书上是用一种 二叉堆的数据结构来实现的
二叉堆
二叉堆 就是一颗被完全填满的二叉树
规定：一：插入的时候 必须先左 到右（先左子树后右子树的插入 ）
二: 父亲要比孩子小；（这个规定是因为我们要最快的找到最小值）
一棵高为h的完全二叉树有2的h次方 到2的h+1次方-1个节点
一个观察发现
可以用一个数组表示 ：对于任意位置i上的元素，其左儿子在2i位置上 右儿子在2i+1的位置上 利用这一个规律可以利用数组来很好的实现一个简单的 优先队列
insert
插入一个数据的时候 在下一个可用位置创建一个空穴，（这个空穴一定要有数据的不然就不是一个完全树)。如果插入的时候没有破坏规则 那么插入成功；若破坏了规则 那么必定是这个数比父亲节点的数据小，将空穴和父亲换一下；当已经平衡了之后或者到了顶部，就将这个数据放入空穴就好了。

7.2.1.png

deleteMin
因为最小的值在第一个 移除就好了 可是麻烦在与 第一个位置空了谁来补充呢？必然是她的子节点 最小值在他们之间（这里不用解释吧。。）然而她们上来后自己的位置又空缺了 那么继续想下找直到没有下面的数据后把最后一个数据填充上去
就好了；

7.2.2.png 7.2.4.png