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.
C++ with a real heap. Using something like std::set instead works, but it's possible with a heap and STL. The problem is designed for learning about heaps, so IMHO using a heap is better than using a set.
The trick is that for delete, you can optimize how you re-heapify the heap after finding and deleting the element. If the new element at the index you deleted is less than the old element, you only need to re-heapify the first half. If it's greater, you only need to re-heapify the second half. https://en.wikipedia.org/wiki/Binary_heap#Delete
Using the "raw" algorithms std::make_heap, std::push_heap, std::pop_heap, etc., rather than std::priority_queue, let you express these optimizations. std::priority_queue doesn't give you enough interface to do them, and also doesn't do them for you.
QHEAP1
You are viewing a single comment's thread. Return to all comments →
C++ with a real heap. Using something like std::set instead works, but it's possible with a heap and STL. The problem is designed for learning about heaps, so IMHO using a heap is better than using a set.
The trick is that for delete, you can optimize how you re-heapify the heap after finding and deleting the element. If the new element at the index you deleted is less than the old element, you only need to re-heapify the first half. If it's greater, you only need to re-heapify the second half. https://en.wikipedia.org/wiki/Binary_heap#Delete
Using the "raw" algorithms std::make_heap, std::push_heap, std::pop_heap, etc., rather than std::priority_queue, let you express these optimizations. std::priority_queue doesn't give you enough interface to do them, and also doesn't do them for you.
This implementation passes all the tests.