Binary Heap Removal

Question

I am just trying to learn a binary heap and doubt that you are doing a delete operation on a binary heap. I read that we can remove an item from the binary heap and we need to refresh it again.

But on the following link, he talks about inaccessibility:

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'm a little confused.

Thanks in advance for all clarifications.

Answer 1

Binary heaps and other priority queue structures do not usually support the general delete item operation; you need an extra data structure that keeps track of every index of the item in the heap, for example. hash table. If you have this, you can implement the general delete operation as

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

Answer 2

Normal deletion is possible, as is DeleteMin / Max. The “problem” is that you need to check both the upper and the lower gears (that is, when the “last” node takes a vacant position, it may be overfulfilled or underestimated. Since it still cannot be both, the obvious reasons, it is easy to verify the correctness.

The only problem that remains is Find. The answer above says that you can find the element in O (log n), but I don't know how to do this. In my implementations, I usually create a bunch of pointers to elements, not elements (cheaper copying during up / down). I add the variable "position" to the Element type, which tracks the index of the Element pointer on the heap. Thus, given element E, I can find its position on the heap in constant time.

Obviously, this is not cut out for every implementation.

Answer 3

I am confused why deleting a binary heap operation is mentioned as not available in the link of your question. An exception in the binary heap is quite possible and this is a composition of two other binary heap operations. https://en.wikipedia.org/wiki/Binary_heap

I consider that you know all other Binary Heap operations

Removing a key from a binary heap requires two lines of code / operation. Suppose you want to delete an element at index x . Decrease its value to the minimum integer. This is Integer.MIN_VALUE . Since this is the lowest value of the whole, it will go to the root position when the decreaseItem(int index, int newVal) done. Then extract the root method that calls extractMin() .

 // 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