# O(lgn) time solution using Priority Queue in Java

• ``````class MedianFinder {

private final PriorityQueue<Integer> left = new PriorityQueue<Integer>(16, Collections.reverseOrder());
private final PriorityQueue<Integer> right = new PriorityQueue<Integer>(16);

private double med;

// Adds a number into the data structure.
public void addNum(int num) {
med = getMedian(num);
}

// Returns the median of current data stream
public double findMedian() {
return med;
}

// insert current element to the left or right heap and get median so far
public double getMedian(final int current) {
final int balance = left.size() - right.size();
double median = med;

// both heaps are of equal size.
if (balance == 0) {
// need to insert in left
if (current < median) {
left.offer(current);
median = left.peek();
}
// need to insert in right
else {
right.offer(current);
median = right.peek();
}
}
// left heap is larger
else if (balance > 0) {
// need to insert in left
if (current < median) {
right.offer(left.poll());
left.offer(current);
}
// need to insert in right
else {
right.offer(current);
}

median = (left.peek() + right.peek()) / 2.0;
}
// right heap is larger
else if (balance < 0) {
// need to insert in left
if (current < median) {
left.offer(current);
}
// need to insert in right
else {
left.offer(right.poll());
right.offer(current);
}

median = (left.peek() + right.peek()) / 2.0;
}

return median;
}
};``````

• I did the same approach using priority queue (heap).

``````class MedianFinder {

private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>();

public MedianFinder() {
minHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return (b - a);
}
});
maxHeap = new PriorityQueue();
}

// Adds a number into the data structure.
public void addNum(int num) {
if(minHeap.size() == 0 || num <= minHeap.peek()) {
} else {
}

balanceHeaps();
}

// Returns the median of current data stream
public double findMedian() {
double median = 0;
if(minHeap.size() == maxHeap.size()) {
median = ((double)minHeap.peek() + (double)maxHeap.peek())/2;
} else {
median = (minHeap.size() > maxHeap.size())? minHeap.peek() : maxHeap.peek();
}
return median;
}

private void balanceHeaps() {
if(minHeap.size() - maxHeap.size() > 1) {