有关一种新的堆。
  • 板块学术版
  • 楼主Graygoo
  • 当前回复31
  • 已保存回复31
  • 发布时间2022/11/23 09:56
  • 上次更新2023/10/27 01:51:57
查看原帖
有关一种新的堆。
535714
Graygoo楼主2022/11/23 09:56

rt,lz昨天在洗澡时候想到的,今天打了一下过了堆的板子。

大概思想是给每个节点设置多个父亲,然后维护一个多叉森林结构,再维护一个没有父亲即可以成为最小值的集合,我称为candidatecandidate

插入的话,把节点加入candidatecandidate即可。

求最大值的话,要对candidatecandidate进行一个我称为uniqueunique的操作,将candidatecandidate随机打乱后进行一个不怎么好描述的过程,具体可以看我的代码。

删除的话,把最大值的儿子能跳到其它父亲的就跳,否则加入candidatecandidate

还有就是合并两堆也很简单,将candidatecandidate放一起即可,不过我没有实现。

代码可以看我在二楼发的云剪贴板。

求大佬分析一下这玩意的期望均摊复杂度,或者给个hack薄纱我?

2022/11/23 09:56
加载中...