社区讨论

有关一种新的堆。

学术版参与者 9已保存回复 31

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
31 条
当前快照
1 份
快照标识符
@lo7hejnf
此快照首次捕获于
2023/10/27 01:51
2 年前
此快照最后确认于
2023/10/27 01:51
2 年前
查看原帖
rt,lz昨天在洗澡时候想到的,今天打了一下过了堆的板子。
大概思想是给每个节点设置多个父亲,然后维护一个多叉森林结构,再维护一个没有父亲即可以成为最小值的集合,我称为candidatecandidate
插入的话,把节点加入candidatecandidate即可。
求最大值的话,要对candidatecandidate进行一个我称为uniqueunique的操作,将candidatecandidate随机打乱后进行一个不怎么好描述的过程,具体可以看我的代码。
删除的话,把最大值的儿子能跳到其它父亲的就跳,否则加入candidatecandidate
还有就是合并两堆也很简单,将candidatecandidate放一起即可,不过我没有实现。
代码可以看我在二楼发的云剪贴板。
求大佬分析一下这玩意的期望均摊复杂度,或者给个hack薄纱我?

回复

31 条回复,欢迎继续交流。

正在加载回复...