LintCode 613: High Five (MinHeap)

1. High Five
   There are two properties in the node student id and scores, to ensure that each student will have at least 5 points, find the average of 5 highest scores for each person.

Example
Given results = [[1,91],[1,92],[2,93],[2,99],[2,98],[2,97],[1,60],[1,58],[2,100],[1,61]]

Return

解法：
利用min-heap，每个学生都分配要给min-heap (size = 5)。

/**
 * Definition for a Record
 * class Record {
 * public:
 *   int id, score;
 *   Record(int id, int score) {
 *     this->id = id;
 *     this->score = score;
 *   }
 * };
 */
class Solution {
public:
    /**
     * @param results a list of <student_id, score>
     * @return find the average of 5 highest scores for each person
     * map<int, double> (student_id, average_score)
     */
    map<int, double> highFive(vector<Record>& results) {
        int len = results.size();
        
        map<int, priority_queue<int, vector<int>, greater<int>> > mp; //id, min-heap
        map<int, double> result;
        for (int i = 0; i < len; ++i) {
            int studentId = results[i].id;
            int studentScore = results[i].score;
            mp[studentId].push(studentScore);
            if (mp[studentId].size() > 5)
                mp[studentId].pop();
        }
        
        for (auto m : mp) {
            double sum = 0;
            while(m.second.size() > 0) {
                sum += m.second.top();
                m.second.pop();
            }
            result[m.first] = sum / 5; //strictly speacking, it needs to check if the student has >= 5 courses
        }
        return result;
    }
};