algorithm – 最小 – 最大堆中的Delete-max操作
发布时间：2020-12-14 19:33:18 所属栏目：Java 来源：网络整理
导读：我正在实现一个min-max堆,一种双端优先级队列.您可以在这里查看 here以获取有关最小 – 最大堆的更多信息. insert和delete-min操作的代码很简单,可以在网上找到.但是,我也试图在min-max堆上实现delete-max操作. 最初,我觉得min-max堆中的delete-max与max-min
|
我正在实现一个min-max堆,一种双端优先级队列.您可以在这里查看
here以获取有关最小 – 最大堆的更多信息.
insert和delete-min操作的代码很简单,可以在网上找到.但是,我也试图在min-max堆上实现delete-max操作. 最初,我觉得min-max堆中的delete-max与max-min堆中的delete-max相同(如果我们考虑包含最大元素的min-max堆的子树,它类似于max-min堆).因此,实现将是简单的,类似于min-max堆的delete-min. 但有个问题： 从上图中可以看出,尽管70是最大元素,但最小 – 最大堆的最后一个元素(12)不在包含70的子树中.因此,我可以用它来替换左子树中留下的间隙删除70后？ 如果我们不使用该元素而是遵循max-min堆的delete-max过程并使用20来替换间隙,则插入堆中的下一个元素将是10的右子,并且永远不会有正确的子元素9. 那么,任何人都可以帮助我吗？ 解决方法
我相信删除最后一级最右边的节点是正确的,并使用它来替换被删除的max元素,即使它在树中交叉.理由如下：
>删除最后一级中最右边的节点不会更改任何需要为该树中的任何节点保留的不变量：所有最低级别的节点仍然小于其所有后代,并且所有节点都处于最大值水平仍然高于他们的后代. 一旦移动了这个节点,就可以在max-min堆中使用正常的fixup过程,以确保左子树不变量仍然成立. 希望这可以帮助！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |