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