删除-MAX操作最小 - 最大堆 [英] Delete-max operation in a min-max heap

问题描述

我在执行最小 - 最大堆型双端优先级队列。你可以看看这里的这里约最小 - 最大堆的更多信息。

I am implementing a min-max heap, a type of double-ended priority queue. You can look here here for more information about min-max heaps.

在code为插入和删除最小操作简单，可在网络上。但是，我也试图执行删除-MAX 的操作和 delete_any_node 在最小 - 最大堆运行。

The code for insertion and delete-min operations are simple and available on the net. But, I am also trying to implement the delete-max operation and delete_any_node operation on a min-max heap.

起初，我觉得删-Max在最小 - 最大堆将是相同删除-MAX的最大最小堆（如果我们考虑包含的最大元素最小 - 最大堆的子树，它类似于一个最大最小堆）。因此，实施将是简单和类似删除最小的最小 - 最大堆。

Initially, I felt that delete-max in min-max heap would be same as delete-max in max-min heap(if we consider the subtree of min-max heap containing the maximum element, it resembles a max-min heap). So, the implementation would be simple and analogous to delete-min of min-max heap.

但是，有一个问题：

But, there is a problem:

可以看出，在上图中，虽然70是最大的元素，的最后一个元素（12）最小 - 最大堆不包含70所以子树，可我用它来代替留在左子树中删除70后的差距？

As can be seen in the above figure, though 70 is the max element, the last element(12) of the min-max heap is not in the subtree containing 70. So, can I use it to replace the gap left in left subtree after deletion of 70?

如果我们不使用这个元素，而是遵循最大最小堆删除-MAX程序，然后用20来替换的差距，在堆中插入的下一个元素将在右子10，永远会有9无权孩子。

If we don't use that element and instead follow delete-max procedure of max-min heap and use 20 to replace the gap, the next element inserted in the heap will be at right child of 10 and forever there will be no right child of 9.

那么，谁能帮助我？这将是慷慨提算法删除任何随机密钥了。

So, can anyone help me? It would be generous to mention the algorithm to delete any random key too.

推荐答案

我相信这是正确的，除去在最后一个级别最右边的节点，并用它来代替已删除的最大元素，即使它跨越了树。的理由如下：

I believe that it is correct to remove the rightmost node on the last level and use it to replace the max element that was removed, even if it crosses in the tree. The rationale is the following:

1. 删除在最后一个级别最右边的节点不会改变任何需要按住该树中的任何节点不变的：所有的分层次的节点仍比所有他们的后代更小，并且所有在最高级别的节点仍然比他们的后代更大。

1. Removing the rightmost node in the last level does not change any of the invariants that need to hold for any nodes within that tree: all of the nodes at min levels are still smaller than all of their descendants, and all of the nodes at max levels are still greater than their descendants.

树仍然是一个完全二叉树。

The tree is still a complete binary tree.

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

Once you have moved this node over, you can then use the normal fixup procedure in a max-min heap in order to ensure that the left subtree invariants still hold.

希望这有助于！

这篇关于删除-MAX操作最小 - 最大堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！