最小 - 最大堆中的删除 - 最大操作

Question

我正在实现一个min-max堆,一种双端优先级队列.您可以在此处查看有关最小 - 最大堆的更多信息.

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.

那么,任何人都可以帮助我吗？

Answer 1

我相信删除最后一层最右边的节点并用它来替换被删除的最大元素是正确的，即使它在树中交叉。理由如下：

1. 删除最后一层中最右边的节点不会改变该树中任何节点需要保持的任何不变量：最小级别的所有节点仍然小于其所有后代以及最大级别的所有节点仍然比他们的后代更伟大。

2. 该树仍然是完全二叉树。

一旦移动了该节点，您就可以在最大-最小堆中使用正常的修复过程，以确保左子树不变量仍然成立。

希望这可以帮助！