5

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.

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 on a min-max heap.

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: enter image description here

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?

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?

nbro
  • 15,395
  • 32
  • 113
  • 196
AvinashK
  • 3,309
  • 8
  • 43
  • 94
  • 3
    Since the question about deleting a random key is different from the question about how to fix up the heap after a delete-max, I would consider asking it as a separate question. – templatetypedef Jan 15 '13 at 06:47
  • @templatetypedef Edited this question to be focused on "how to delete the maximum element". You can now find a specific question with a proposed solution on "how to remove any node from a min-max heap" here: http://stackoverflow.com/q/39392864/3924118 – nbro Sep 08 '16 at 14:09

1 Answers1

3

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. 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.

  2. 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.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • This is how I implemented it, too, when I wrote a min-max-heap data structure a few months ago. (+1) – Erik P. Jan 15 '13 at 14:34
  • This works to remove the _maximum_ element in the min-max heap, but are you sure this works for any node in the min-max heap? If yes, which "fixup" would you use exactly? Using a "trickle-down" operation would not work, check the only comment I made to this gist which shows the problem: https://gist.github.com/gnarmis/4647645 – nbro Sep 07 '16 at 19:49