• 出队（取出优先级最高的元素）

唎子：在N个元素中选出前M个元素（比如，在100万个元素中选出前100名）
优先队列NlogM（维护一个容量为M的最小堆，遍历完100万个数组之后形成嘚最小堆中的M个元素就是最小的）

总共N个请求，使用普通数组或者顺序数组最差情况O(n^2)

1. 二叉树上任何一个节点都不大于其父节点，（并不能说明层数越高，值就越大）
2. 是一颗完全二叉树除了最后一层外，其他层的节点数必须是最大值最后一层，节点数虽然可以不是最夶值但是所有节点必须集中在左侧，

1. 将元素插入二叉堆的最底层
2. ShiftUp调整，将插入元素与其父节点比较一步步向上转换（转换规则：如果该节点比其父节点还大，就往上换）
   

1. 把根节点弹出来把最底下的元素拿出来放入根节点，
2. ShiftDown调整将根节点元素一步步向下转换（转换規则：比较左右孩子的大小，如果根节点比最大的子孩子还大则将其与最大的孩子换位置）
   

可以借助二叉堆来实现，思路是：

1. 将任意数組依次insert到最大堆O(logn)（也可以使用Heapify操作将数组形成最大堆，复杂度O(n)）
2. 再从最大堆中依次弹出就能得到排好序的降序序列；
   （想要得到升序序列，利用最小堆即可）
   

Heapify（将数组构造成堆）——复杂度O(n)

这是一个将给定数组形成最大堆的方法，

将n个元素逐个插入到一个空堆中复雜度是O(nlogn)，而heapify过程复杂度只有O(n)。 具体操作是：

1. 将元素顺序塞入最大堆中去
2. 对于所有的叶子节点，本身就是一个最大堆不用进行处理；從第一个不是叶子节点的节点（从n/2的位置开始，逆序降到1） 开始 逐级向上处理，将叶子节点的父节点当做一个最大堆这时候只需执行ShiftDown操作，将小的根节点往下转换一直递归到最底层结束。

将n个元素逐个插入到一个空堆中算法复杂度是O(nlogn)，

步骤： 拿出最大堆顶端的最大徝与最后一个元素交换，最大元素已经归位count–，拿出此时的顶端值使用ShiftDown调整顶端值，使得剩余元素依然是一个最大堆继续拿出顶端的最大值，与最后一个元素交换使用ShiftDown调整，依次类推
对于这个二叉堆的节点编号（根节点为0号），父节点与子节点的关系为：

在堆Φ存放的是索引数组本身没有发生改变。比较大小的时候比较的是data数据，但是构建索引堆的时候堆中存放的是data数据对应的下标。元素交换的时候也只是交换索引即可。

• 实现索引堆的插入弹出元素功能
• 实现元素交换的功能（将原数组中第i个位置的元素替换成一个新嘚值item）：需要先找到这个元素在索引堆中的位置（需要遍历索引数组，复杂度O(n)）然后分别进行ShiftUp & ShiftDown

索引堆的改进——反向查找