Write a C function that deletes an arbitrary element from a max heap (the delete

Question

Write a C function that deletes an arbitrary element from a max heap (the deleted element may be anywhere in the heap). The resulting heap must satisfy the max heap definition. What is the computing time of your function? (Hint: Change the priority of the element to one greater that that of the root, use the change priority function of Exercise 3, and then pop.) Read file as input to build Max Heap Tree. Set input file: 7,16,49,82,5,31,6,2,44 Output: Max Heap: 82 49 31 44 5 16 6 2 7 Delete?: Y Choice: 31 Max Heap: 82 49 16 45 5 7 6 2 Time: 0.00123 sec Exit: Y Press any key to continue...

Explanation / Answer

Actually, you can remove an item from the middle of a heap without trouble. The idea is to take the last item in the heap and, starting from the current position (i.e. the position that held the item you deleted), sift it up if the new item is greater than the parent of the old item. If it's not greater than the parent, then sift it down.

That's the procedure for a max heap. For a min heap, of course, you'd reverse the greater and less cases.

Finding an item in a heap is an O(n) operation, but if you already know where it is in the heap, removing it is O(log n).

I published a heap-based priority queue for DevSource a few years back. See A Priority Queue Implementation in C# . It has a RemoveAt method that does exactly what I described.

Actually, you can remove an item from the middle of a heap without trouble. The idea is to take the last item in the heap and, starting from the current position (i.e. the position that held the item you deleted), sift it up if the new item is greater than the parent of the old item. If it's not greater than the parent, then sift it down.

That's the procedure for a max heap. For a min heap, of course, you'd reverse the greater and less cases.

Finding an item in a heap is an O(n) operation, but if you already know where it is in the heap, removing it is O(log n).

I published a heap-based priority queue for DevSource a few years back. See A Priority Queue Implementation in C# . It has a RemoveAt method that does exactly what I described.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.