Search code examples
algorithmpseudocode

Try to understand delete-min of Min-Max Heap

I want to understand how the process of min-max heap deletion work, I've searched the pseudo-code of it but found nothing, and it seems like I cannot ask for the pseudo-code here. So here is my problem

g0

Can anyone show the logic of "delete of min element 7" at least let me know how the pseudo-code "feel like"?

Edit: In case people think I try nothing here is another slide:

  1. [1.1] I don't understand:

    (4-th line): ... and then reinsert into the min-max heap.

    Is the "reinsert" here calling the original insertion procedure? Or it just mean the cases following it?

    [1.2]

    (8-th line): The smallest key in the min-max heap is one of the children or grandchildren of the root.

    I'm not sure whether the "grandchildren" recursively include their grandchildren.

    Slide: g1

I can understand the "VerifyMax" procedure used in insertion, not sure whether this procedure will be used in deletion...:

enter image description here

Solution

  • The algorithm "feels like" the DeleteMin procedure of an ordinary min-heap (or the DeleteMax procedure for a max-heap):

    1. Replace the current min (that is, the first element in the heap) with last element in the heap.
    2. Decrease the size of the heap by one.
    3. Use the TrickleDown procedure on the first element in order to restore the heap property.

    TrickleDown is slightly more complicated, but not much: you need to check both min and max relationships. Usually this is done by checking both children and grandchildren of the trickled element.