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.
Actually, you can achieve logarithmic O(log n) time for removal of arbitrary elements.
What I did was store the indicies of certain values in a dictionary, then when I wanted to remove a value, I'd have the index of that item in the array.
To remove some element, simply overwrite the value of the item in the array you want to remove with the value of last item in the heap (going top to bottom, left to right), and then remove the last item in the heap. The index can found by the dictionary lookup. Then all you have to do is "re-heapify" from that index. Dictionary lookups are constant, so the removal operation is on the same order as re-heapifying (i.e. swapping all items in the heap until the heap property is satisfied); an O(log n) operation.
I had implemented a linear removal operation, but it timed out so I resorted to this. I'd be happy to explain further if you all are interested.
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 →
Actually, you can achieve logarithmic O(log n) time for removal of arbitrary elements.
What I did was store the indicies of certain values in a dictionary, then when I wanted to remove a value, I'd have the index of that item in the array.
To remove some element, simply overwrite the value of the item in the array you want to remove with the value of last item in the heap (going top to bottom, left to right), and then remove the last item in the heap. The index can found by the dictionary lookup. Then all you have to do is "re-heapify" from that index. Dictionary lookups are constant, so the removal operation is on the same order as re-heapifying (i.e. swapping all items in the heap until the heap property is satisfied); an O(log n) operation.
I had implemented a linear removal operation, but it timed out so I resorted to this. I'd be happy to explain further if you all are interested.