HighFiveScore

Question:

We have a bunch of Results, you can treat each Result as a node, with the data structure below:

class Result {
    int id;
    int value;

    public Result(int id, int value) {
        this.id = id;
        thid.value = value;
    }
}

What we want is to compute the average of the five highest score of each student.

我们可以用Heap来解决这个问题，要求最大的5个，那么我们可以维护一个大小为5的最小堆。每次遇到一个新值，如果heap未到容量，那么一律加入；如果到达容量，那么只有当前值比peek()更大时，才删除peek()并加入新值。

代码可以写成如下的样子： Below is Java version:

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Created by RuiG on 11/18/16.
 */
public class FiveHigh {

    public static Map<Integer, Double> getFiveHigh(Result[] src) {

        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        Map<Integer, Double> ansMap = new HashMap<>();
        final int capacityLimit = 5;


        for (Result res: src) {
            int key = res.id;
            int val = res.value;

            if (!map.containsKey(key)) {
                map.put(key, new PriorityQueue<>());
            }

            PriorityQueue<Integer> pq = map.get(key);
            if (pq.size() < capacityLimit) { // add if less than capacity
                pq.offer(val);
            } else if (val > pq.peek()) { // remove peek and insert new value
                pq.poll();
                pq.offer(val);
            }
        }

        // compute average score
        for (Integer key: map.keySet()) {
            PriorityQueue<Integer> pq = map.get(key);
            int sum = 0;
            while (!pq.isEmpty()) {
                sum += pq.poll();
            }
            ansMap.put(key, sum / 5.0);
        }

        return ansMap;
    }

    public static void main(String[] args) {
        Result r1 = new Result(1, 100);
        Result r2 = new Result(1, 90);
        Result r3 = new Result(1, 40);
        Result r4 = new Result(1, 10);
        Result r5 = new Result(1, 30);
        Result r6 = new Result(1, 60);

        Result r7 = new Result(2, 6);
        Result r8 = new Result(2, 6);
        Result r9 = new Result(2, 7);
        Result r10 = new Result(2, 6);
        Result r11 = new Result(2, 6);

        Result[] src = {r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11};

        Map<Integer, Double> ans = getFiveHigh(src);

        for (int key: ans.keySet()) {
            System.out.println("id: " + key + ", value: " + ans.get(key));
        }
    }
}

class Result {
    int id;
    int value;

    public Result(int id, int value) {
        this.id = id;
        this.value = value;
    }
}