Interview Question:
Edited Below You are given an array. You make 2 heaps out of it, one minheap and the other max heap. Now find the median of the array using these 2 provided heaps in O(nlog n) time.
Corrected Question Numbers are randomly generated and stored into an (expanding) array. How would you keep track of the median?
Solution This problem can be solved using 2 heaps and the median can always be accessed in O(1) time.
Here's how you use both heaps. Note that I'm assuming you don't know the number of elements, and this is why we must pop until we pop something from the min heap that is larger than or equal to what we pop from the max heap. Note that we return the average because in the case of a set like {1, 2, 3, 4} the median is actually 2.5 (the average of the two "middle" values). I'm assuming double as the value type, but this can obviously be anything. Here:
double min = minheap.pop();
double max = maxheap.pop();
while(min < max) {
min = minheap.pop();
max = maxheap.pop();
}
return (min + max) / 2;
Since popping is O(log n) and we have to pop O(n / 2) values, this is O(n log n).
{1, 2, 3}. Pop gives min as 1 and max as 3. Pop again gives min as 2 and max as 2. Condition min < max fails so we return (min + max) / 2 = 2. I challenge you to provide an example where this algorithm fails. –
Canaan min as 1 and max as 2. Condition min < max is okay, so proceed to next iteration. Pop gives min as 2 and max as 2 (yes, again, that's how a heap works). Condition min < max fails so return (min + max) / 2 = 2. –
Canaan Heap object and the only method you have access to is getMin(), so there's no way to inspect the underlying data structure to find N. Then, I guess, two heaps is the only way. I'm going to go look at other questions now :) –
Xl A working implementation in java, using 2 heaps, O(n log n). At any time I keep the two heaps balanced in size (ie. they differ at most by 1, if we entered n elements such that n%2==1). Getting the median is O(1). Adding a new element is O(log n).
public class MedianOfStream {
private int count;
private PriorityQueue<Integer> highs, lows;
public MedianOfStream() {
highs = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg0.compareTo(arg1);
}
});
lows = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
});
}
private int getMedian() {
if (count == 0)
return 0;
if (lows.size() == highs.size()) {
return (lows.peek() + highs.peek()) / 2;
} else if (lows.size() < highs.size()) {
return highs.peek();
}
return lows.peek();
}
private void swap(){
int h = highs.poll();
int l = lows.poll();
highs.add(l);
lows.add(h);
}
public int updateMedian(int n) {
count++;
if (count == 1)
lows.add(n);
else if (count==2) {
highs.add(n);
if(highs.peek()<lows.peek()) {
swap(); // O(log n)
}
}
else {
if (n > highs.peek()) {
lows.add(highs.poll()); // O(log n)
highs.add(n); // O(log n)
} else {
highs.add(lows.poll()); // O(log n)
lows.add(n); // O(log n)
}
if(highs.peek()<lows.peek()) {
swap(); // O(log n)
}
}
// if we added an even # of items,
// the heaps must be exactly the same size,
// otherwise we tolerate a 1-off difference
if (Math.abs(lows.size() - highs.size()) > (count % 2)) {
if (lows.size() < highs.size()) {
lows.add(highs.poll()); // O(log n)
} else {
highs.add(lows.poll()); // O(log n)
}
}
return getMedian(); // O(1)
}
}
Popping from a heap is an O(log N) operation, so you can achieve O(N log N) by popping half the elements from one of the heaps and taking the last popped value (you'd have to handle edge cases). This doesn't take advantage of the other heap though.
You can achieve O(N) using the selection algorithm, but the constant factor is very high. The former suggestion is probably better if you already have a heap.
Here's a python implementation for it. I tested some of the examples generated using Random.org and tested them on median finder most of them seem to work.
import heapq
def medianFinder(arr):
minHeap = []
maxHeap = []
def handleMedianFinder(num: int):
if not len(maxHeap):
heapq.heappush(maxHeap, -num)
return -maxHeap[0]
elif not len(minHeap):
heapq.heappush(minHeap, num)
return (minHeap[0]-maxHeap[0])/2
if num < minHeap[0]:
if len(maxHeap) > len(minHeap):
oldMedian = -heapq.heappop(maxHeap)
heapq.heappush(minHeap, oldMedian)
heapq.heappush(maxHeap, -num)
return (minHeap[0]-maxHeap[0])/2 if (len(minHeap) + len(maxHeap))%2 == 0 else minHeap[0]
heapq.heappush(maxHeap, -num)
elif num > -maxHeap[0]:
if len(maxHeap) < len(minHeap):
oldMedian = heapq.heappop(minHeap)
heapq.heappush(maxHeap, -oldMedian)
heapq.heappush(minHeap, num)
return (minHeap[0]-maxHeap[0])/2 if (len(minHeap) + len(maxHeap))%2 == 0 else -maxHeap[0]
heapq.heappush(minHeap, num)
else: # between the medians (new medians)
if len(maxHeap) < len(minHeap):
oldMedian = heapq.heappop(minHeap)
heapq.heappush(maxHeap, -oldMedian)
heapq.heappush(minHeap, num)
else:
oldMedian = -heapq.heappop(maxHeap)
heapq.heappush(minHeap, oldMedian)
heapq.heappush(maxHeap, -num)
if len(minHeap) < len(maxHeap):
return minHeap[0]
elif len(maxHeap) < len(minHeap):
return -maxHeap[0]
return (minHeap[0]-maxHeap[0])/2
for num in arr:
# print('maxHeap => ', maxHeap)
# print('minHeap => ', minHeap)
print(handleMedianFinder(num))
arr1 = [11, 18, 16, 12, 14, 4, 15, 10, 19, 20]
medianFinder(arr1)
JavaScript solution using two heaps:
function addNewNumber(minHeap, maxHeap, randomNumber) {
if (maxHeap.size() === minHeap.size()) {
if (minHeap.peek() && randomNumber > minHeap.peek()) {
maxHeap.insert(minHeap.remove());
minHeap.insert(randomNumber);
} else {
maxHeap.insert(randomNumber);
}
} else {
if (randomNumber < maxHeap.peek()) {
minHeap.insert(maxHeap.remove());
maxHeap.insert(randomNumber);
} else {
minHeap.insert(randomNumber);
}
}
}
function getMedian(minHeap, maxHeap) {
if (!maxHeap.size()) {
return 0;
}
if (minHeap.size() === maxHeap.size()) {
return (minHeap.peek() + maxHeap.peek()) / 2;
} else {
return maxHeap.peek();
}
}
© 2022 - 2024 — McMap. All rights reserved.