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.
By looking at the code from aboves, the heaps are implemented with sorted array only, and they have to sorted it out when inserting too. This is as same complexity as sorted array, just they mannually splitted into two.
Although they use two sorted arrays, but it doesn't really improve the insertion complexity from O(N) to O(logN).
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
By looking at the code from aboves, the heaps are implemented with sorted array only, and they have to sorted it out when inserting too. This is as same complexity as sorted array, just they mannually splitted into two.
Although they use two sorted arrays, but it doesn't really improve the insertion complexity from O(N) to O(logN).
This is my understanding, might be wrong..