DATA STRUCTURE BRAINSTORM 1 : Keep Track of Median

Trick -> Simply run through a list of data structures and try to apply each one.


Numbers are randomly generated and stored into an (expanding) array How would you keep track of the median?

Data Structure Brainstorm:

Linked list? Probably not – linked lists tend not to do very well with accessing and sorting numbers

Array? Maybe, but you already have an array Could you somehow keep the elements sorted? That’s probably expensive Let’s hold off on this and return to it if it’s needed.

Binary tree? This is possible, since binary trees do fairly well with ordering In fact, if the binary search tree is perfectly balanced, the top might be the median But, be careful – if there’s an even number of elements, the median is actually the average of the middle two elements The middle two elements can’t both be at the top This is probably a workable algorithm, but let’s come back to it.

Heap? A heap is really good at basic ordering and keeping track of max and mins This is actually interesting – if you had two heaps, you could keep track of the biggest half and the smallest half of the elements The biggest half is kept in a min heap, such that the smallest element in the biggest half is at the root The smallest half is kept in a max heap, such that the biggest element of the smallest half is at the root Now, with these
data structures, you have the potential median elements at the roots If the heaps are no longer the same size, you can quickly “re-balance” the heaps by popping an element off the one heap and pushing it onto the other.

Heap is the best solution in our cases. I have already posted a heap sort implementation to support the solution. 

Following is my solution for the problem :



public class Median {
public static int maxCount = 0;
public static int minCount = 0;

/**
* @param args
*/
public static void main(String[] args) {
ArrayList<Integer> ar = gyle.random.RandomList.generateRandromList(9);
heapSort(ar);

ArrayList<Integer> arMin = new ArrayList<Integer>();
ArrayList<Integer> arMax = new ArrayList<Integer>();
for (int i = 0; i < ar.size() / 2; i++) {
// if (maxCount > minCount) {
insertMinHeap(arMin, ar.get(i));
minCount++;
}
for (int i = ar.size() / 2; i < ar.size(); i++) {
insertMaxHeap(arMax, ar.get(i));
maxCount++;
}

System.out.println("Min " + arMin);
System.out.println("max" + arMax);
System.out.println(findMedian(arMin, arMax));
boolean choice = true;

while (choice) {
System.out.println("Please the number");
Scanner s = new Scanner(System.in);
Integer number = s.nextInt();
/**
* do logics
*/
if (number < arMin.get(0) && number > arMax.get(0)) {
System.out.println("MID OF TWO");
if (minCount < maxCount) {
arMin.add(0, number);
minCount++;
} else {
arMax.add(0, number);
maxCount++;
}

} else {
if (number > arMin.get(0)) {
System.out.println("SHOULD BE IN MIN HEAP of larger numbers");
if (minCount <= maxCount) {
gyle.binarysearch.HeapSort.insertMinHeap(arMin, number);
minCount++;
} else {
int temp = arMin.get(0);
arMin.remove(0);
gyle.binarysearch.HeapSort.insertMinHeap(arMin, number);
arMax.add(0, temp);
maxCount++;
}

} else {
if (number <= arMax.get(0)) {
System.out.println("SHOULD BE IN MAX HEAP of smaller number");
if (minCount > maxCount) {
gyle.binarysearch.HeapSort.insertMaxHeap(arMax,
number);
maxCount++;
} else {
int temp = arMax.get(0);
arMax.remove(0);
gyle.binarysearch.HeapSort.insertMaxHeap(arMax,
number);
arMin.add(0, temp);
minCount++;
}
}

}

}
/**
* ask again
*/

System.out.println("MI -->" + arMin);
System.out.println("MX -->" + arMax);
System.out.println(findMedian(arMin, arMax));
System.out.println("Wanna add more?(true/false)");
choice = s.nextBoolean();
}

}

private static int findMedian(ArrayList<Integer> arMin,
ArrayList<Integer> arMax) {
if (arMax.size() > arMin.size()) {
return arMax.get(0);
} else {
if (arMax.size() == arMin.size()) {
return (arMax.get(0) + arMin.get(0)) / 2;
} else {
return arMin.get(0);
}
}
}
}