5

我正在实现一个最小最大堆，一种双端优先级队列。您可以在这里查看有关最小-最大堆的更多信息。

插入和删除最小操作的代码很简单，可以在网上找到。但是，我也在尝试在最小最大堆上实现删除最大操作。

最初，我觉得 min-max heap 中的 delete-max 与 max-min heap 中的 delete-max 相同（如果我们考虑包含最大元素的 min-max heap 的子树，它类似于 max-min heap）。因此，实现将简单且类似于 min-max 堆的 delete-min。

但有个问题： 在此处输入图像描述

从上图中可以看出，虽然70是最大元素，但是最小-最大堆的最后一个元素（12）不在包含70的子树中。那么，我可以用它来替换左子树中留下的间隙吗删除70后？

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

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

4

1 回答 1

3

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

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

  2. 这棵树仍然是一棵完全二叉树。

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

希望这可以帮助！

于 2013-01-15T06:47:01.440 回答