优先队列跟常见的队列不一样。队列就是先进先出，优先队列是根据优先值大小决定出的顺序。

实现优先队列，先考虑简单的方式。
使用无序链表：

  • 插入O(1)
  • 弹出O(n)

使用有序链表：

  • 插入O(n)
  • 弹出O(1)

因此，我们需要一种更加均衡的数据结构，能使得插入弹出都为O(lgN)。
使用AVL树，红黑树的话显得小题大作。于是二叉堆就派上用场了，在这里它简单高效又稳定。

二叉堆

堆可以分为小顶堆，大顶堆。这里以小顶堆为例。

定义

任意节点的key小于该节点两个子节点的满二叉树。

存储

由于是满二叉树，所以可以用数组存储。
索引0处不存储数据的话，索引i处节点的父节点在i/2，左子节点在2i，右子节点在2i+1

API

  1. NewBinHeap(cap int) *BinHeap
  2. NewBinHeapWitArray(arry []int, cap int) *BinHeap
  3. (h *BinHeap) Insert(k int) (ok bool)
  4. (h *BinHeap) DelMin() int
  5. (h *BinHeap) Size() int

实现

下滤

当某节点需要下滤，则让它与小儿子节点比较，若大于小儿子则交换位置，迭代执行到小于小儿子或成为叶子为止。

优化一下：
一次交换操作会发生3次赋值操作，n次交换会有3n次赋值。其实可以只进行n+2次赋值。
当索引i处的节点需要下滤，先把arry[i]保存到一个临时变量k。然后把i处节点看作一个空穴，设它的小儿子的索引为s，若k大于arry[s]，则执行arry[i]=arry[s]，然后索引s处看作空穴（执行 i = s）。直到arry[s]大于k或空穴位于叶子，执行arry[i]=k

  1. func (h *BinHeap) percolateDown(i int) {
  2.     arry := h.arry
  3.     k := arry[i]
  4.     cavIdx := i
  5.     for {
  6.         if cavIdx*2 > h.size {
  7.             break
  8.         }
  9.         smallC := cavIdx * 2
  10.         if smallC != h.size && arry[smallC+1] < arry[smallC] {
  11.             smallC++
  12.         }
  13.         if arry[smallC] > k {
  14.             break
  15.         }
  16.         arry[cavIdx] = arry[smallC]
  17.         cavIdx = smallC
  18.     }
  19.     arry[cavIdx] = k
  20. }

上滤

当某节点需要上滤，则让它与父节点比较，若小于父节点则交换位置，迭代执行到大于父节点或成为根节点为止。

也可以像下滤一样优化：

  1. func (h *BinHeap) percolateUp(i int) {
  2.     arry := h.arry
  3.     k := arry[i]
  4.     cavIdx := i
  5.     for ; arry[cavIdx/2] > k; cavIdx /= 2 {
  6.         h.arry[cavIdx] = h.arry[cavIdx/2]
  7.     }
  8.     arry[cavIdx] = k
  9. }

Insert

插入满二叉树最后一个位置，然后上滤

DelMin

  1. 把根节点的值放入临时变量min
  2. 将满二叉树最后一个节点的值放到根节点
  3. 数组size减1
  4. 根节点下滤
  5. 返回min

NewWithArray

对arry[len(arry)/2]至arry[1]依次执行下滤

分析：
此操作乍一看时间复杂度好像是O(NlgN)，但这个界太弱了。
叶子不需要下滤，所以需要下滤的只有N/2个节点。且只有根节点需要下滤lgN，其他的皆小于lgN

实际上时间复杂度为O(N)，证明如下：
image.png

应用

堆排序

复杂度 O(NlgN)

求解TopK问题

以求解TopK大的元素为例，使用小顶堆

方式1:
用数组前K个元素建立一个小顶堆，用数组余下的大于当前堆顶元素的元素替换当前堆顶元素并下滤。
复杂度O(K+NlgK)

方式2:
像堆排序那样所有元素建立一个小顶堆，不过只弹出K个元素
复杂度O(N+KlgN)

左式堆

二叉堆简单，但是存在不能很好支持merge的问题。二叉堆用数组存储，merge时需要大量移动操作导致效率低下。且merge后难以保证是满二叉树，不能再用数组存储，需要用指针指向儿子。还有merge后怎么保证平衡性？

定义

零路径长(NPL)：节点到只有一个或零个儿子的节点的最短距离

左式堆：任意节点满足左儿子NPL不小于右儿子NPL的堆

定理

  1. 左式堆的右路径即零路径
  2. 设左式堆的右路径上有r个节点，则堆至少有2-1个节点（数学归纳法证明）

实现

Merge

  1. func merge(h1, h2 *node) *node {
  2.     if h1 == nil {
  3.         return h2
  4.     }
  5.     if h2 == nil {
  6.         return h1
  7.     }
  8.     if h1.k < h2.k {
  9.         h1.merge1(h2)
  10.         return h1
  11.     }
  12.     h2.merge1(h1)
  13.     return h2
  14. }
  16. func (h *node) merge1(h1 *node) {
  17.     if h.left == nil {
  18.         h.left = h1
  19.         return
  20.     }
  21.     h.right = merge(h.right, h1)
  22.     if h.left.k < h.right.k {
  23.         h.left, h.right = h.right, h.left
  24.     }
  25.     h.npl = h.right.npl + 1
  26. }
  1. 当h1<h2时，h2与h1的右儿子merge，否则h1与h2的右儿子合并。这能保证合并之后不破坏堆的特性。
  2. 回溯时，若右儿子的NPL大于左儿子的NPL，则交换两个儿子。这能保证左式堆的特性。真实目的其实是在防止右子树过长，尽量保证平衡。

Insert

即将一个左式堆与一个只有一个节点的左式堆合并

DelMin

删除根节点，然后合并根节点的左右儿子

NewWithArray

先把数组初始化为二叉堆，然后根据二叉堆建立左式堆

二项队列

支持Merge，且Insert的复杂度达到常数级别

二项树

image.png
二项树B是由两个B连在一起，也可以看作由BB…B和一个根节点连在一起。

特点：

  1. 两个B合并即得到一个B，且合并很简单。
  2. B拿去根节点之后，得到BB…B
  3. B的节点个数为2

是专门为堆的操作而设计的

但是特点3意味着B的大小是固定的，但是堆可能会随时Insert以及DelMin，无法保证个数始终为2

然而 a2+b2+c2+d2…+n*2可以表示所有整数！

定义

二项队列由若干个二项树组成，且每个二项树满足堆的性质

实现

将这若干个二项树放到一个数组中。设数组长度为len，则二项队列的最大容量为2-1（即len个bit位能表示的最大值）。

Merge

当PQ1合并PQ2时，将两个二项树数组对应位置的二项树合并。注意当PQ1.trees[i]与PQ2.trees[i]都不为空时，合并得到一个B需要暂时放到变量carry中，在合并PQ1.trees[i+1]与PQ2.trees[i+1]时考虑，且只需要一个carry就够了。
因此，任一次二项树合并有8种可能情况：PQ1.trees[i]为nil或不为nil， PQ2.trees[i]为nil或不为nil，carry为nil或不为nil。
这里代码可以用到类似于文件权限表示、类似bitmap的技巧：

  1.     var carry *node
  2.     for i := 0; i <= max(bq.MaxTrees(), bq1.MaxTrees()); i++ {
  3.         switch bq.hasTree(i) + bq1.hasTree(i)*2 + notNil(carry)*4 {
  4.         case 2:
  5.             bq.trees[i] = bq1.trees[i]
  6.         case 3:
  7.             carry = merge(bq.trees[i], bq1.trees[i])
  8.             bq.trees[i] = nil
  9.         case 4:
  10.             bq.trees[i] = carry
  11.             carry = nil
  12.         case 5:
  13.             carry = merge(carry, bq.trees[i])
  14.             bq.trees[i] = nil
  15.         case 6:
  16.             fallthrough
  17.         case 7:
  18.             carry = merge(carry, bq1.trees[i])
  19.         default: // case 0, case 1
  20.         }
  21.     }

Insert

即将一个含一个元素的优先队列合并到另一个优先队列中。

根据Merge的过程可知，插入过程会在二项树数组中第一个空位处停止，随机模型下每一个位置为空的概率为1/2，二项树合并次数为n的概率为(1/2)，且合并次数与队列大小无关，插入会在常数时间内停止。

DelMin

找到所有二项树中根节点最小的那颗，假设是B二项树，弹出并删除根节点，剩下子树生成含BB…B二项树的优先队列，然后合并到原队列中。