优先队列

绪论

优先队列也可以称之为堆，分为大根堆和小根堆。堆的用处很多，最常见的也就是所谓的堆排序，可以发现也是利用了树的思想去做的。

也许用图表达更合适（图片是引用了一下 leetcode 的图，我做不出这么优美的动图）。

堆：符合以下两个条件之一的完全二叉树：

根节点的值 ≥ 子节点的值，这样的堆被称之为最大堆，或大顶堆；

根节点的值 ≤ 子节点的值，这样的堆被称之为最小堆，或小顶堆。

明确的基础的概念之后可以思考一下堆排序。首先将数列构建成一个大根堆，按照性质大根堆的堆顶一定是数组中最大的元素，所以我们可以每次将堆顶的元素换到最后面去，然后重新构建一次大根堆，以此类推就会得到一个排序好的数组。

初始化堆

首先谈谈如何初始化堆。

1. 情况 1: 一个一个插入元素，依次构建堆

2. 情况 2: 将一个数组构建堆

我们可以从下标 1 开始当做根节点，那么数组的长度为 N+1（N 为原数组长度）设根节点为 i，那么 公式可以得出

i = 1;

left = i*2;

right = left+1;

不妨思考一下这两种情况的复杂度，空间复杂度来说可以直接给出结论，是 O(1),基本是在原数组构建完全二叉树。那么实际复杂度呢？

第一种情况

思考一个这样的情况（最坏的情况，大根堆），每次插入的元素都是当前序列中最大的元素,由于是数组，那么每次插入都是 append 在末端。那么会造成什么样的情况呢？

当前节点会沿着树的拓扑一直往上浮，树的度为 M，那么树的高度是 logM ，不妨称之为 N，那么意味着当前会在树结构中上浮 N 次。那么参考这张图

此时树的高度为 3，底层每个节点往上浮动的数量都是当节点的深度,所以在高度为 3 的的堆每次插入节点最坏的情况就是 28，N=13，logn=3~4 最大上浮次数是 28 不妨先定义为 push 的操作是 O(logn)）

所以我们可以得出每次插入节点上浮的复杂度 O(n*logn)

第二种情况

思考一下，如果初始化就是一个数组的情况下，我们会怎么构建这个堆？莫非还是一个个遍历插入吗？显然不会这样做，会有更聪明的办法。

参考第一种情况，既然自底向上上浮不好，那么下沉呢？我们要的结果是降低复杂度，所以思考一下树的结构会发现，树的深度越深，那么节点的数量越多，这些结果都是上浮那么复杂度会很高，但是如果是下沉，那么最深的节点已经在最深处了，就不需要下沉了。

参考这段代码

func Init(h Interface) {
// heapify
 n := h.Len() //h认为是一个数组
for i := n/2 - 1; i >= 0; i-- {
down(h, i, n) //down 下沉
}
}

看看他的语义，获取数组的长度为 n，for 循环中每次都下沉，但是 i 是 n/2-1。所以真正的优化就是在这，参考这张图。

使用二分的思想。先从从树的中间往下下沉（自底向上的下沉），可以发现，最末尾节点无需下沉。每个节点下沉的大小刚好是他的高度。

看看结果，构建一个堆的复杂度为 O(n),达到了一个还不错的线性复杂度。

分析代码

说了那么多理论不贴代码怎么行，不过 golang 有提供 heap 的 package，这里就贴一下源码就行。然后解释解释。

h 理解为一个数组，有 3 个方法。Less 作比较的，swap 交换元素 Len 获取当前元素大小

两段最重要的代码

up 顾名思义上浮，按照之前的公式，j 为当前节点，首先获取他的父亲节点

j-1/2 得到父亲节点的下标

如果当前节点大于 parent，那么交换，以此类推直到达到合适的位置或者到了根节点。此时上浮结束。时间复杂度为 O(logn),基本就是树的高度了。

顾名思义这段代码是下沉的代码。看起来还挺多的，但是仔细思考一下还是很简单的。

先获取当前节点的左孩子 j1，先判断是否大于数组长度了，即已经到尾巴了，还会判断数据是否溢出（想的周到啊宝）。之后再判断左孩子是否大于右孩子，如果是则直接和 parent 比较，如果大于那么 parent 下沉，继续和左右孩子比较，交换，直到合适的位置。

复杂度为 O(logn)

思考一下为什么下沉还有返回一个 bool？

push 操作

直接 push 到数组尾部，然后上浮即可，复杂度同 up

pop 操作

其实删除操作就比较有意思，在我的印象里，无论是什么树，只要这棵树有一定特性，那么删除就一定不会简单（实名 diss 红黑）。

可以看看具体代码，还是很简单的，将堆顶的元素删除，从数组末尾换一个新节点上来，然后下沉到对应的位置即可

但是还有一段代码可以瞧瞧，remove 和 pop 不一样，pop 是直接弹出堆顶，remove 是删除堆中指定某个位置的元素。

我们瞧瞧具体代码，如果是数组末尾，则直接 pop 删除掉就行了，如果不是，则将数组末尾的值和需要删除的节点调换位置，然后判断是否需要下沉！，如果不需要下沉则上浮。这就是为什么 down 的需要返回一个 bool 的原因。

Fix 操作

fix 操作类似 update，修改堆中元素的值，然后判断是否需要浮动

谈谈实际应用

除了堆排序我们可以看看在实际应用会这么使用堆这个数据结构

直接给出答案，首先初始化堆，然后一次 pop，当 pop 到第 k 次的时候就是最大第 k 个。

再来看看第二题

这这道题我们思考一下合并 3 个链表，怎么用到堆呢？平时是不是都是数组？

其实思路也很简单，把链表的头当做单独的元素构建堆。比如此时构建的堆是

【1，1，2】

每次 pop 元素的时候把当前堆顶指向下一个元素，然后重置堆。

比如 pop 1 这个元素 ，那么把堆顶 1 变成他的 next 4 重置堆就变成了

【1，2，4】

看到这里我相信已经明白了具体思路了。

总结

基本记录是完成了，由于总结的比较少第一次总结这多可能会有写到导致写错的地方，如果发现请指出，或许有哪些地方描述与您所期望的不符也可以留言一下，共同进步。