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.

Rms

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.

Peralta

Thanks Larsmans! It means binary heap is only good for sorting data on their priority basis. – Rms

Which PQ structures support lgn deletion? – Maiocco

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.

Gadmon

Answer 3

I am confused why delete operation of binary heap is mentioned as unavailable in the link of your question. Deletion in binary heap quite possible and it's composition of 2 other operations of binary heap. https://en.wikipedia.org/wiki/Binary_heap

I am considering you know all other operations of Binary Heap

Deleting a key from binary heap requires 2 lines of code/operation. Suppose you want to delete item at index x. Decrease it's value to lowest integer possible. That's Integer.MIN_VALUE. Since it's lowest value of all integer it will go to root position when decreaseItem(int index, int newVal) execution done. Afterwards extract the root invoking extractMin() method.

// Complexity: O(lg n)
public void deleteItem(int index) {
    // Assign lowest value possible so that it will reach to root
    decreaseItem(index, Integer.MIN_VALUE);
    // Then extract min will remove that item from heap tree. correct ?
    extractMin();
}

Full Code: BinaryHeap_Demo.java

Tamboura