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.
I implemented a classic heap from scratch with same semantics as Python3 heapq, but was still failing 2 test cases.
The problem was the delete was taking too long since it requires a linear search to find the element position to be deleted.
To optimize, I just created a lookup dict from the value to the index of the element, in which I can easily start a deletion in O(1) and finish it in O(log n).
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 →
I implemented a classic heap from scratch with same semantics as Python3 heapq, but was still failing 2 test cases.
The problem was the delete was taking too long since it requires a linear search to find the element position to be deleted.
To optimize, I just created a lookup dict from the value to the index of the element, in which I can easily start a deletion in O(1) and finish it in O(log n).