We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
"This question is designed to help you get a better understanding of basic heap operations."
Query 2 - Delete the element u from the heap " .. sigh...
Deleting arbitrary value from a heap / priority queue is not a basic operation the heap is designed for. Heaps rep. invariant only guarantees a constant time access to min/max element. Arbitrary deletion is done via swapping a node (which first has to be found in linear time) with the last element, plus then everything "below" it has to be fixed (worst case log(n) time) to garantee heap properties. Anything better than that can be implemented as a BST or a hashmap(?), but that effectively makes it a BST or a hashmap and not a conventional heap. No offence, just my 2 cents.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
QHEAP1
You are viewing a single comment's thread. Return to all comments →
Deleting arbitrary value from a heap / priority queue is not a basic operation the heap is designed for. Heaps rep. invariant only guarantees a constant time access to min/max element. Arbitrary deletion is done via swapping a node (which first has to be found in linear time) with the last element, plus then everything "below" it has to be fixed (worst case log(n) time) to garantee heap properties. Anything better than that can be implemented as a BST or a hashmap(?), but that effectively makes it a BST or a hashmap and not a conventional heap. No offence, just my 2 cents.