Algorithms and Data Structures · Senior · Question 74 of 75
What does the "two heaps" trick fail to support efficiently, compared with a balanced BST?
- ✓Correct answer: Removing an arbitrary element from the middle
- 2Reading the current median in O(1) time
- 3Inserting a new element in O(log n) time
Explanation
Heaps can only remove their root cheaply. For a sliding window median you need lazy deletion (marking removed values and skipping them later) or an ordered multiset, such as a balanced tree, that removes any value in O(log n).