Skip to content

Lecture 5 Binomial Queue

:material-circle-edit-outline: 约 995 个字 :material-clock-time-two-outline: 预计阅读时间 3 分钟

最后一次数据结构课

Priority Queue

优先队列不是按照顺序出来，而是按照优先级，比如最大的/最小的。

常见的有堆

Binomial Queue

定义

二项队列是一个二项树的集合（森林），且每一个高度的二项树最多只能有一个

  • 高度为0的二项树只有一个结点。
  • 高度为k的由两个k-1的合成

二项树带有堆的顺序性质（任意子树最大/最小key在根节点）。

image-20240327085955294

性质

二项树性质

两颗树比根节点大小，大的（或小的）作为另一个的子树根节点

image-20240327090022378

k是高度，一个节点高度为0

二项队列与二进制

知道一些条件可以确定唯一二项队列

image-20240325101636475

  • 在一个二项队列这个森林里，每一高度的树要不没有，要不只有一颗（有两颗必须合并）。
    • 所以任意高度的树只有0个1两种情况
    • 所以可以用二进制表示二项队列，并进行运算
  • 而二项树的总结点数正好满足\(2^k\)的规律
    • 所以bin表示的dec即二项队列的总节点数

操作

FindMin

image-20240327083908357

最小堆顺序的情况下，每颗二项树的minKey都是root，只需要比较logN个根节点即可

优化：储存最小的根节点，每次有改变都进行检测与更新

Merge

做算法忌讳的就是算法里有不确定的地方

image-20240327084303249

两个二项队列合并很确定，直接二进制树加法

三个就会有不确定的地方，先是哪两个合并？这里需要double check

有时候无所谓，有时候有所谓

对于FindMin，合并哪两个无所谓，因为最小的一定还是根

Insert

实际上就是merge从1开始

image-20240325103854430

DeleteMin

delete的套路就是转化为merge

image-20240327090214714

删除最小的根，将这个根下的子树当成新的二项队列，与原来的剩下的队列进行合并

H’’需要被放到一个新的数组，即遍历每一个root

把所有数据结构都写一次

期末考试必考，之前考过写AVL树代码

Implementation

二项队列用数组实现

二项树的实现

树有两个常见的表示法

  1. 正常的
  2. 左儿子右兄弟

前者随机访问儿子速度快，但是空间开销大，因为多个儿子需要多个指针

后者随机访问儿子慢一点，但空间开销小，因为每个结点都只需要两个指针

选择哪个需要考虑

二项树没有随机访问儿子的需求，所以这里选后者实现

  • 左儿子右兄弟
    • 每个node依旧两个指针，一个指向原来最左边的儿子，一个指向兄弟

不过还有个问题一直没解决，合并两个二项树的时候被合并的树应该放在左儿子还是右儿子的位置

也就是说，同一排的兄弟应该按什么顺序排列

首先得知道的是，合并的两棵树是一样大的，也就是说

如果递增顺序的话，被合并的是最大的，导致要前往放其的位置需要遍历到最后面

但是递减的话就能很快了

看下面两个二项树（注意这里是普通形式，自行转化为左儿子右兄弟形式），根节点下面的子树即递增顺序，最左边只有一个结点，最右边的子树有4个结点。

image-20240327091847040

这个就是递减顺序且正确形式的二项树

image-20240327092050933

总结一下刚刚的两个点：形式与顺序

image-20240327091717063

代码

数据结构

image-20240327092200788

MergeTree

image-20240327092536571

image-20240327092550913

MergeQuene

image-20240327092937596

从低位往高位遍历合并，不懂就类比二进制加法

DeleteMin

包含四个步骤

image-20240327094105085

均摊分析

插入分析

使用聚合法

这里没看

image-20240327094354948

image-20240327094509428