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.
It is because if you have one heap(in form of an array), it does NOT guarantee you to have a 'median' when you look for the very middle element of the array.
You can check this array, [2,4,3,6,5]. It is a heap that means it's a complete binary tree. However, element '3' is not a median, which is 4.
Of course, if you 'heapsort' an array, you only need one array. However, time complexity is then O(nlog(n)). When we use two heaps(min & max), we only need to push value and heapify them. In this case, those two take O(1) and O(log(n)) each. This is a lot faster than sorting which is not needed in this challenge.
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
This is what I understood.
It is because if you have one heap(in form of an array), it does NOT guarantee you to have a 'median' when you look for the very middle element of the array.
You can check this array, [2,4,3,6,5]. It is a heap that means it's a complete binary tree. However, element '3' is not a median, which is 4.
Of course, if you 'heapsort' an array, you only need one array. However, time complexity is then O(nlog(n)). When we use two heaps(min & max), we only need to push value and heapify them. In this case, those two take O(1) and O(log(n)) each. This is a lot faster than sorting which is not needed in this challenge.