rt,lz昨天在洗澡时候想到的,今天打了一下过了堆的板子。
大概思想是给每个节点设置多个父亲,然后维护一个多叉森林结构,再维护一个没有父亲即可以成为最小值的集合,我称为candidate。
插入的话,把节点加入candidate即可。
求最大值的话,要对candidate进行一个我称为unique的操作,将candidate随机打乱后进行一个不怎么好描述的过程,具体可以看我的代码。
删除的话,把最大值的儿子能跳到其它父亲的就跳,否则加入candidate。
还有就是合并两堆也很简单,将candidate放一起即可,不过我没有实现。
代码可以看我在二楼发的云剪贴板。
求大佬分析一下这玩意的期望均摊复杂度,或者给个hack薄纱我?