Question

Create a java code that will take user input and find the median using two heaps (max and min heap). The two heap must sort the elements from small to large. Running time must be efficient and below O(n^2). The algorithm must support the following methods:

- insert(b): insert a given element b in O(logn) time

- getMedian(): return the median in O(1) time

- removeMedian(): remove and return the median in O(logn) time

Note: The median will return the element that exist in the list, for example an even number of elements <9, 9, 1, 2> will return 2 instead of 5 which doesn't exist in the list.

Odd list exp <4, 8, 2> will return 4 (sorting <2,4,8>). Another even exp <15, -2, 10, -5, 11, 18, 5, 1> will return 5 (sorting <-5, -2, 1, 5, 10, 11, 15, 18>)

Answer with java or pseudo code and analyse the running time.

Answer 1

CODE

import java.util.Scanner;

import java.util.PriorityQueue;

import java.util.Collections;

// - We use 2 Heaps to keep track of median

// - We make sure that 1 of the following conditions is always true:

// 1) maxHeap.size() == minHeap.size()

// 2) maxHeap.size() - 1 = minHeap.size()

public class Main {

private static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // keeps track of the SMALL numbers

private static PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // keeps track of the LARGE numbers

  

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

System.out.println("enter the number of integers: ");

int n = scan.nextInt();

for (int i = 1; i <= n; i++) {

System.out.println("Enter the number " + i + " : ");

insert(scan.nextInt());

}

scan.close();

  

System.out.println("The median is: " + getMedian());

System.out.println("Removing median: " + removeMedian());

}

  

private static void insert(int n) {

if (maxHeap.isEmpty()) {

maxHeap.add(n);

} else if (maxHeap.size() == minHeap.size()) {

if (n < minHeap.peek()) {

maxHeap.add(n);

} else {

minHeap.add(n);

maxHeap.add(minHeap.remove());

}

} else if (maxHeap.size() > minHeap.size()) {

if (n > maxHeap.peek()) {

minHeap.add(n);

} else {

maxHeap.add(n);

minHeap.add(maxHeap.remove());

}

}

// maxHeap will never have fewer elements than minHeap

}

  

private static double getMedian() {

if (maxHeap.isEmpty()) {

return 0;

}

return maxHeap.peek();

}

  

private static double removeMedian() {

if (maxHeap.isEmpty()) {

return 0;

}

return maxHeap.poll();

}

}

The complexity of median finding is O(N log N), as we need to read the stream, and due to heap insertions/deletions.