Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I think I'm confused about deletion in heaps, and since I have an exam today, I'm looking for your help to correct me.

I will post photos since it will makes it a bit more clear.

Note(forget about deleting the root)

enter image description here

What I understand is that , heaps only deletes the root element or the top. So, I made 2 solutions and I'm kindly asking which solution is the correct one.

enter image description here

Q:the heapness will be violated, I will have to replace it by the rightmost element bottom down right? (32) enter image description here

share|improve this question
    
It's hard to get what you are doing. But from my understanding the second pictures looks right. In the first picture: what whould be your final heap? –  A.Schulz Nov 28 '12 at 10:08
    
I'm sorry for that, I tried my best, in the first pic I'll have to do precolate/bubble operations to achieve the heap property again. I think you confirm it. Me too thinking is that the second approach is the correct one. –  Sobiaholic Nov 28 '12 at 11:09
add comment

2 Answers

up vote 3 down vote accepted

A min-heap typically only supports a delete-min operation, not an arbitrary delete(x) operation. I would implement delete(x) as a composition of decrease-key(x, $-\infty$), and delete-min. Recall, that to implement decrease-key, you would bubble up the element to maintain the heap property (in this case all the way to the root). In a binary heap, to implement the delete-min operation, you replace the root by the last element on the last level, and then percolate that element down.

To summarize, to delete(x), bubble-up the element all the way to the root, then delete the element and put the last element in the heap at the root, then percolate down to restore the heap property.

share|improve this answer
add comment

There's no need to bubble-up the element all the way to the root. You can replace the item to be removed with the last element in the heap. If that new element is less than its parent, then bubble it up. If it's greater than its children, bubble it down.

I implemented this in my DevSource article, A Priority Queue Implementation in C#. Full source is available at http://www.mischel.com/pubs/priqueue.zip.

See my Stack Overflow answer about this at http://stackoverflow.com/a/8706363/56778

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.