Skip to content

Instantly share code, notes, and snippets.

@sxwebdev

sxwebdev/medianHeap.java

Created September 30, 2019 13:21
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sxwebdev/0e4d541c7caeb564f7e4f20e601661bf to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sxwebdev/0e4d541c7caeb564f7e4f20e601661bf to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @gostave gostave created this gist Dec 11, 2017.
    75 changes: 75 additions & 0 deletions medianHeap.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,75 @@
    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;

    public class Solution {
    /**
    * The add number method
    */
    public static void addNumber(int num, PriorityQueue<Integer> lowers, PriorityQueue<Integer> highers) {
    if(lowers.size() == 0 || num < lowers.peek()) {
    lowers.add(num);
    } else {
    highers.add(num);
    }
    }
    /**
    * The rebalance method
    */
    public static void rebalance(PriorityQueue<Integer> lowers, PriorityQueue<Integer> highers) {
    PriorityQueue<Integer> biggerHeap = lowers.size() > highers.size() ? lowers : highers;
    PriorityQueue<Integer> smallerHeap = lowers.size() > highers.size() ? highers : lowers;
    if(biggerHeap.size() - smallerHeap.size() >= 2) {
    smallerHeap.add(biggerHeap.poll());
    }
    }
    /**
    * The get median method
    */
    public static double getMedian(PriorityQueue<Integer> lowers, PriorityQueue<Integer> highers) {
    PriorityQueue<Integer> biggerHeap = lowers.size() > highers.size() ? lowers : highers;
    PriorityQueue<Integer> smallerHeap = lowers.size() > highers.size() ? highers : lowers;
    if(biggerHeap.size() == smallerHeap.size()) {
    return ((double)biggerHeap.peek() + smallerHeap.peek())/2;
    } else {
    return biggerHeap.peek();
    }
    }
    /**
    * The get medians method
    */
    public static double[] getMedians(int[] array) {
    PriorityQueue<Integer> lowHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
    public int compare(Integer a, Integer b) {
    return -1 * a.compareTo(b);
    }
    });
    PriorityQueue<Integer> highHeap = new PriorityQueue<Integer>();
    double[] medians = new double[array.length];
    /**
    * The loop
    */
    for(int i=0; i < array.length; i++){
    int number = array[i];
    addNumber(number,lowHeap,highHeap);
    rebalance(lowHeap,highHeap);
    medians[i] = getMedian(lowHeap,highHeap);
    System.out.println(medians[i]);//this is the running median
    }
    return medians;
    }
    /**
    * The main
    */
    public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] a = new int[n];
    for(int i=0; i < a.length; i++){
    a[i] = in.nextInt();
    }
    getMedians(a);
    }
    }