在min-max堆中删除-max操作

Question

我正在实现一个min堆，它是一种双结束优先级队列.有关max堆的更多信息，您可以在这里查看这里。

插入和删除-min操作的代码很简单，可以在网络上使用。但是，我也试图在min堆上实现删除-max操作。

最初，我认为min堆中的删除-max与max-min堆中的删除-max相同(如果我们考虑包含最大元素的min堆的子树，它类似于max-min堆)。因此，实现简单且类似于删除max堆的-min.

但是，有一个问题：

​

如上图所示，虽然70是max元素，但max堆的最后一个元素(12)不在包含70的子树中。所以，我可以用它来代替删除70后左子树中留下的空隙吗？

如果我们不使用该元素，而是按照max-min堆的删除-max过程并使用20替换间隙，那么插入堆中的下一个元素将位于10的右子元素，并且永远不会有正确的9子元素。

有人能帮我吗？

Answer 1

我认为在最后一个级别上删除最右边的节点并使用它替换已删除的max元素是正确的，即使它在树中交叉。理由如下：

1. 删除最后一层中最右边的节点并不会改变该树中任何节点需要保持的不变量:最小级别上的所有节点仍然比它们的所有后代都小，最高级别上的所有节点仍然大于它们的后代。
2. 这棵树仍然是一个完整的二叉树。

一旦移动了这个节点，就可以在max-min堆中使用常规的固定过程，以确保左子树不变量仍然有效。

希望这能有所帮助！