0

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

Improve this question
3
  • 1
    Could this help? cglab.ca/~morin/teaching/5408/refs/minmax.pdf Commented Dec 21, 2018 at 18:11
  • 1
    What do you mean you found "nothing"? There's tons of articles out there on this. Commented Dec 21, 2018 at 18:39
  • Did you look at the paper in the link from גלעד ברקן? That has lots of pseudocode. (Also, I always think you should work from texts which don't misspell class names like Elemetn -- a clear sign that the code wasn't tested -- and which are written in a language in which the author is fluent.) But anyway: yes, grandchild means precisely grandchild, nothing more, and reinsert probably means the code from the heap construction. Commented Dec 22, 2018 at 1:29

3 Answers 3

Reset to default
1

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.

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

7 Comments

@ptr_user: wikipedia -- despite everything, still a useful resource -- calls it push-down and DownHeap is also a common name. The name isn't important. (The Wikipedia article also had pseudocode. I didn't review it, though.)
May I ask you a question on the paper \@גלעדברקן provided: Only the (precise) grandchild nodes are considered because odd-levels are min-heap and the min heap property on odd level is preserved after deletion of the last node on the complete tree? (assume root_level=1)
I meant I'm thinking about why only child and grandchild should be considered in the pseudocode of the paper's TrickleDownMin(i) method.
@ptr_user7813604: because of the heap constraint, just the same as an ordinary heap. You know that the grandchildren of the grandchildren are smaller (or larger if you're using the max levels) than the grandchildren, so why would you need to check it again? The only element that violates the constraint is the one you're trying to place,
Sorry, I pasted the wikipedia link from an Android. Try this one: en.wikipedia.org/wiki/Min-max_heap (hint: if it happens to you again, delete the m. from the mobile URL.)
|
0

  1. Replace "7" with "90" (Replacing the min element with last element) and decrease the size of min-max heap.

  2. Swap "90" with "9" (Since it is the minimum now). Now "9" is the root.

  3. Swap "90" with "70" as max heap property is violated.

  4. Swap "70" with "20" as min heap property is violated. This is the final result.

Improve this answer

2 Comments

@jim, no they need to swap 90 with 70 at step 3 to preserve the max for level 2. Then 70 will be swapped with 20.
@ptr_user7823604: perhaps they thought it went without saying, given that you are deleting an element
0

Now I'm very sure the confusion after I understand the min-max heap:

  1. It's not the same as the original insert method of min-max heap

  2. It means exactly the grandchild, not recursively. Since grandchild is on min-level.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.