quantiles

quantiles

import java.util.*;

class Pair {
    public int val;
    public int cnt;
    public Pair(int v, int c) {
        this.val = v;
        this.cnt = c;
    }
}

class PairComparator implements Comparator<Pair> {
    @Override
    public int compare(Pair x, Pair y) {
        return x.val - y.val;
    }
}

public class Main {
    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        int Q = 3;
        int M = 4;
        int[] pairs = {1, 2, 2, 2, 3, 4, 5, 3};
        int N = 0;
        Queue<Pair> minHeap = new PriorityQueue<Pair>(M, new PairComparator());
        while (M > 0){
            int value = pairs[2 * M - 2];
            int cnt = pairs[2 * M - 1];
            N += cnt;
            Pair p = new Pair(value, cnt);
            minHeap.offer(p);
            M--;
        }
        int popCnt = 0;
        for (int k = 1; k < Q; ++k) {
            int lk = (N * k + 1) / Q;
            lk -= popCnt;
            while (minHeap.size() > 0) {
                Pair top = minHeap.peek();
                if (top.cnt >= lk) {
                    System.out.println(top.val);
                    break;
                } else {
                    lk -= top.cnt;
                    minHeap.poll();
                    popCnt += top.cnt;
                }
            }
        }
    }
}