Skip to content

Lesson5：二项队列

二项队列是堆序树的森林，每个树都是二项树，二项树的度数是树的高度。

B0是一个一节点的树。

Bk就是两个Bk-1，其中一个的根节点连到另一个根节点。

alt text

Bk有k个孩子，分别为B0->Bk-1，有2k个节点，深度为d的节点数为(k,d)

操作

找最小

最小值为root之一，由于至多logN取上个root，所以时间复杂为O(logN)。

我们也可以记录最小的数据并在其被改变的时候上传，这一时间复杂度为O(1)。

合并

首先是一个二进制的加法，man!

1代表有某一树，0代表没有。 比如下图，就是(110)2+(111)2 = (1011)2。

alt text

然后就是比较谁的根节点大，大的合并到小的，因为是最小堆。

插入

e.g. insert 1-7 to it :

1->2然后3，所以1->2->3->4，然后5->6，单走一个7。

alt text

二项队列森林从空进行N次插入最坏为O(N)，平均为常数时间。

删除最小

  1. 找到最小 O(logN)

  2. 将Bk移除二项队列。 O(1)

  3. 删除其最大的。 O(logN)

  4. 将其与剩下的合并。 O(logN)

这就是我天才的思路呀，你们有没有这么天才的设计(不是)。

作业

alt text

4 如果是 2 的子结点，说明 23 对应子树保持为 B2，不参与 merge。

这给我们什么启发呢？这个合并是渐进的，不是并行的，前面的合并完了，才轮到后面更高阶的。

引用

https://zhoutimemachine.github.io/note/courses/ads-hw-review/#hw5