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

我正在实现最小最大值堆，这是一种双端优先级队列。你可以看这里here关于最小最大堆的更多信息。最小最大堆中的删除最大值操作

插入和删除分钟操作的代码很简单，可以在网上获得。但是，我也试图在最小 - 最大堆上执行delete-max操作。最初，我觉得min-max堆中的delete-max与max-min堆中的delete-max相同（如果我们考虑包含最大元素的min-max堆的子树，它类似于max-分钟堆）。因此，实现将很简单，类似于min-max堆的delete-min。

但是，有一个问题： enter image description here

如在上面的图中可以看出，虽然图70是最大元件，最后元件（12）的最大 - 最小堆的不包含70的子树。那么，我可以用它来代替删除70后留在左侧子树中的空位吗？

如果我们不使用该元素，而是遵循最大最小堆的删除-MAX程序，并使用20来代替差距，插在堆中的下一个元素将是在10和永远正确的孩子将没有右边的孩子9.

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

来源

2013-01-15 avinash

由于关于删除随机密钥的问题与如何在delete-max之后修复堆的问题不同，因此我会考虑将其作为一个单独的问题。 – templatetypedef

@templatetypedef编辑此问题以关注“如何删除最大元素”。现在，您可以在此处找到一个关于“如何从最小 - 最大堆中删除任何节点”的建议解决方案的具体问题：http://stackoverflow.com/q/39392864/3924118 – nbro

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

删除最右边的节点在最后一个级别不会改变任何需要保持在树中的任何节点不变的：所有的分层次的节点仍小于他们的所有后代，以及所有最高级别的节点都比他们的后代更大。
该树仍然是一个完整的二叉树。

一旦搬到这个节点上，您就可以使用正常的修正过程中的最大最小堆，以确保左子树不变量仍持有。

希望这会有所帮助！

来源

2013-01-15 06:47:01 templatetypedef

这也是我实现它的方式，当时我几个月前写了一个min-max-heap数据结构。（+1） –

这可以删除最小 - 最大堆中的_maximum_元素，但是您确定这适用于最小 - 最大堆中的任何节点吗？如果是的话，你会准确使用哪个“fixup”？使用“滴入”操作不起作用，请检查我对此问题所做的唯一评论，其中显示问题：https：//gist.github.com/gnarmis/4647645 – nbro

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

回答

相关问题