Deletion in binary heap

Question

I am just trying to learn binary heap and have a doubt regarding doing delete operation in binary heap. I have read that we can delete an element from binary heap and we need to reheapify it.

But at the following link, it says unavailable:

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

                Binary Search  AVL Tree   Binary Heap (min)  Binomial Queue (min)

Find            O(log n)       O(log n)   unavailable         unavailable
Delete element  O(log n        O(log n)   unavailable         unavailable

I am little confused about it.

Thanks in advance for all of the clarifications.

Answer 1

Binary heaps and other priority queue structures don't usually support a general "delete element" operation; you need an additional data structure that keeps track of each element's index in the heap, e.g. a hash table. If you have that, you can implement a general delete operation as

• find-element, O(1) expected time with a hash table
• decrease key to less than the minimum, O(lg n) time
• delete-min and update the hash table, O(lg n) combined expected time.

Answer 2

A regular delete is possible, just like a DeleteMin/Max. The "problem" is that you have to check for both up- and downshifts (i.e.: when the "last" node takes up the vacant spot, it can be over- or underevaluated. Since it still can't be both, for obvious reasons, it's easy to check for correctness.

The only problem that remains is the Find. The answer above states that you can Find Element in O(lg n), but I wouldn't know how. In my implementations, I generally build a Heap of pointers-to-elements rather than elements (cheaper copying during up/downshifts). I add a "position" variable to the Element type, which keeps track of the index of the Element's pointer in the Heap. This way, given an element E, I can find it's position in the Heap in constant time.

Obviously, this isn't cut out for every implementation.