CC-5 : Given a list of sorted numbers, find the median.

Description:

Given a list of sorted integers as find their median.

Test cases and expected outputs:

Input Parameters	Expected outputs
Sorted integers input list:3,9, 14, 19, 30, 45, 70	Median: 19
Sorted integers input list:3,9, 14, 19, 30, 45, 70, 80	Median: 24

Pseudocode:

Initialize a PriorityQueue instance named smallerHeap to be used as min Heap.

Initialize a PriorityQueue instance named largerHeap to be used as max Heap.

We have list of sorted numbers as input, which we will add to the above heaps one by one using the below method:

InsertToHeaps(num) method:

Add number to smallerHeap.

Add top element of smallerHeap to largerHeap.

If largerHeap size is > smallerHeap size, then remove top element from largerHeap and add to smallerHeap.

getMedian() method:

After calling insertToHeaps() for all input numbers, call getMedian method to find the median.

If largerHeap size is not equal to smallerHeap size, then median is top element of smallerHeap, so extract the same and return it.

Else if largerHeap size is equal to smallerHeap size, then median (tope element of smallerHeap + top element of largerHeap)/2. Calculate and return this value.

Code:

	
PriorityQueue<Integer> smaller= new PriorityQueue<Integer>();
PriorityQueue<Integer> larger= new PriorityQueue<Integer>(Collections.reverseOrder());
 
public void insertToHeaps(int num) {
	smaller.add(num);
	larger.add(smaller.remove());
	if (larger.size() > smaller.size()) {
		smaller.add(larger.remove());
	}
}

public int getMedian() {
	if (larger.size()!=smaller.size()){
		return smaller.element();
	}
	int median=(smaller.element()+larger.element())/2;
	return median;
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Collections;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class HeapFindMedian {
	
PriorityQueue<Integer> smaller= new PriorityQueue<Integer>();
PriorityQueue<Integer> larger= new PriorityQueue<Integer>(Collections.reverseOrder());
 
public void insertToHeaps(int num) {
	smaller.add(num);
	larger.add(smaller.remove());
	if (larger.size() > smaller.size()) {
		smaller.add(larger.remove());
	}
}

public int getMedian() {
	if (larger.size()!=smaller.size()){
		return smaller.element();
	}
	int median=(smaller.element()+larger.element())/2;
	return median;
}

public static void printQueue(Queue<Integer> queue, String label) throws Exception   {
    if (queue.size() == 0) { System.out.println("Queue empty"); return; }
    System.out.println();
	System.out.println("******************************************************************");
	System.out.print(label +": ");
	Iterator itr=queue.iterator();
	while (itr.hasNext())  {
	    System.out.print(itr.next());
	    System.out.print(" <- ");
	} 
	System.out.println();
	System.out.println("******************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
 	try {
	HeapFindMedian hp=new HeapFindMedian();
	hp.insertToHeaps(3);
	hp.insertToHeaps(9);
	hp.insertToHeaps(14);
	hp.insertToHeaps(19);
	hp.insertToHeaps(30);
	hp.insertToHeaps(45);
	hp.insertToHeaps(70);
	printQueue(hp.smaller, "Smaller Priority Queue");
	printQueue(hp.larger, "Larger Priority Queue");
	retVal=hp.getMedian();
	System.out.print("Median: "+ retVal);
	
	hp.insertToHeaps(80);
	printQueue(hp.smaller, "Smaller Priority Queue");
	printQueue(hp.larger, "Larger Priority Queue");
	retVal=hp.getMedian();
	System.out.print("Median: "+ retVal);
		
 	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}