堆和优先队列优先队列( 四 )

之后我们找到这个堆中第一个非叶子节点，这个节点的位置始终是数组的数量除以2，也就是索引5位置的27，从这个节点开始，对每一个非叶子的节点,，进行shift down操作。
27比它的子节点51要小，所以交换二者。
接下来我们看索引2位置的20 。首先呢，我们需要将20与它两个子节点中较大的51交换。
每个节点堆化的时间复杂度是O(logn)，那个节点的堆化的总时间复杂度是O(nlogn) 。
推导过程
堆化节点从倒数第二层开始。堆化过程中，需要比较和交换的节点个数与这个节点的高度k成正比。
所以 heapify() 时间复杂度是 O(n).
建堆后，数组中的数据是大顶堆。把堆顶元素，即最大元素，跟最后一个元素交换，那最大元素就放到了下标为n的位置。
这个过程有点类似上面的“删除堆顶元素”的操作，当堆顶元素移除之后，把下标n的元素放堆顶，然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆。一直重复这个过程，直到最后堆中只剩下下标为1的元素，排序就完成了。
topk和selectk问题既可以使用快排思想解决，也可以使用优先队列解决。
快排:O(n) 空间O(1)
优先队列:O(nlogk) 空间O(k)
优先队列的有i是，不需要一次性知道所有数据,数据流的方式处理。
优先队列我们知道普通队列的特点是先进先出，但是优先队列的特点则遵守以下两条规则：
- 最大优先队列：无论入队的顺序，当前最大的元素先出列。
- 最小优先队列：无论入队的顺序，当前最小的元素先出列。
说明：在学习优先队列前必须先理解二叉堆
这时候就是二叉堆发挥作用的时候了。我们知道二叉堆有以下特性：
- 最大堆：堆顶是整个数组中最大的元素，且任何父节点的值都大于其子节点
- 最小堆：堆顶是整个数组中最小的元素，且任何父节点的值都小于其子节点
对于优先队列，介绍以下几种操作：
入队操作；
出队操作；
说明：以最小优先队列为例
1.入队操作
优先队列本质上就是用二叉堆来实现的，每次插入一个数据都是插入到数据数组的最后一个位置，然后再做上浮操作，如果插入的数是数组中最大数，自然会上浮到堆顶。如“图1 入队操作”所示：
2.出队操作
出队操作就是返回堆顶最小堆的数据之后用数组最后的数插入到堆顶，之后再做下沉操作。如“图2 出队操作”所示：
因为二叉堆上浮和下沉的时间复杂度都为log2(n)，所以入队和出队的时间复杂度也是log2(n) 。
优先队列是基于二叉堆实现的，优先指的是按某种优先级优先出列而不是先入先出。操作系统的阻塞机制正是有优先队列实现。

堆和优先队列 优先队列( 四 )

秒懂生活扩展阅读

堆和优先队列优先队列( 四 )