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?

Improve this question
2
  • 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. Commented Jan 15, 2013 at 6: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: stackoverflow.com/q/39392864/3924118 Commented Sep 8, 2016 at 14:09

1 Answer 1

Reset to default
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!

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This is how I implemented it, too, when I wrote a min-max-heap data structure a few months ago. (+1)
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: gist.github.com/gnarmis/4647645

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.