CODEWITHSUNDEEP
algorithm
Sajjad
Sajjad

Reputation: 237

Delete ith node from a Heap

I know that deleting a node from a heap is O(log n) that occures at the root. And I also know that deleting an arbitrary node in a heap in one of the heap tree problems and is O(n).

Is there any algorithm that reduces the running time of deleting the Ith node from a maxheap to O(log n) where I is ranging from 1 to N?

Upvotes: 1

Views: 1469

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133995

The expensive part of deleting an arbitrary node from a heap isn't in the deleting, but in finding the node to delete. Actually deleting the node is O(log n). But first you have to do a sequential scan of the underlying data store in order to find the node. That's the O(n) part.

The only way to speed this up is to keep a second data structure like a dictionary or hash map or similar that can quickly tell you where the item is in the backing store. Then you have an O(1) lookup in the dictionary, an O(1) removal from the dictionary, and an O(log n) removal from the heap.

Upvotes: 4

Related Questions