Delete-max operation in a min-max heap

Question

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:

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?

Answer 1

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!