High Five

class Solution {
public:
    vector<vector<int>> highFive(vector<vector<int>>& items) {
        map<int, priority_queue<int, vector<int>, greater<int>>> top5;
        for (auto& it : items) {
            auto& pq = top5[it[0]];
            pq.push(it[1]);
            if ((int)pq.size() > 5) pq.pop();
        }
        vector<vector<int>> ans;
        for (auto& [id, pq] : top5) {
            int sum = 0;
            while (!pq.empty()) { sum += pq.top(); pq.pop(); }
            ans.push_back({id, sum / 5});
        }
        return ans;
    }
};

import (
    "container/heap"
    "sort"
)

type minHeap []int

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *minHeap) Pop() interface{} {
    old := *h
    n := len(old)
    v := old[n-1]
    *h = old[:n-1]
    return v
}

func highFive(items [][]int) [][]int {
    top5 := map[int]*minHeap{}
    for _, it := range items {
        id, score := it[0], it[1]
        h, ok := top5[id]
        if !ok {
            h = &minHeap{}
            top5[id] = h
        }
        heap.Push(h, score)
        if h.Len() > 5 {
            heap.Pop(h)
        }
    }
    ids := make([]int, 0, len(top5))
    for id := range top5 {
        ids = append(ids, id)
    }
    sort.Ints(ids)
    ans := make([][]int, 0, len(ids))
    for _, id := range ids {
        h := top5[id]
        sum := 0
        for _, v := range *h {
            sum += v
        }
        ans = append(ans, []int{id, sum / 5})
    }
    return ans
}

import heapq
from collections import defaultdict
from typing import List

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        top5: dict = defaultdict(list)
        for student_id, score in items:
            heapq.heappush(top5[student_id], score)
            if len(top5[student_id]) > 5:
                heapq.heappop(top5[student_id])
        ans: List[List[int]] = []
        for student_id in sorted(top5.keys()):
            ans.append([student_id, sum(top5[student_id]) // 5])
        return ans

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    peek() { return this.h[0]; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l] < this.h[s]) s = l;
                if (r < n && this.h[r] < this.h[s]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function highFive(items) {
    const top5 = new Map();
    for (const [id, score] of items) {
        if (!top5.has(id)) top5.set(id, new MinHeap());
        const heap = top5.get(id);
        heap.push(score);
        if (heap.size() > 5) heap.pop();
    }
    const ids = [...top5.keys()].sort((a, b) => a - b);
    const ans = [];
    for (const id of ids) {
        const heap = top5.get(id);
        let sum = 0;
        for (const v of heap.h) sum += v;
        ans.push([id, Math.floor(sum / 5)]);
    }
    return ans;
}

class Solution {
    public int[][] highFive(int[][] items) {
        TreeMap<Integer, PriorityQueue<Integer>> top5 = new TreeMap<>();
        for (int[] it : items) {
            PriorityQueue<Integer> pq = top5.computeIfAbsent(it[0], k -> new PriorityQueue<>());
            pq.offer(it[1]);
            if (pq.size() > 5) pq.poll();
        }
        int[][] ans = new int[top5.size()][2];
        int i = 0;
        for (Map.Entry<Integer, PriorityQueue<Integer>> e : top5.entrySet()) {
            int sum = 0;
            for (int v : e.getValue()) sum += v;
            ans[i][0] = e.getKey();
            ans[i][1] = sum / 5;
            i++;
        }
        return ans;
    }
}

class MinHeap {
    h: number[] = [];
    size(): number { return this.h.length; }
    push(v: number): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): number | undefined {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l] < this.h[s]) s = l;
                if (r < n && this.h[r] < this.h[s]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function highFive(items: number[][]): number[][] {
    const top5 = new Map<number, MinHeap>();
    for (const [id, score] of items) {
        if (!top5.has(id)) top5.set(id, new MinHeap());
        const heap = top5.get(id)!;
        heap.push(score);
        if (heap.size() > 5) heap.pop();
    }
    const ids = [...top5.keys()].sort((a, b) => a - b);
    const ans: number[][] = [];
    for (const id of ids) {
        const heap = top5.get(id)!;
        let sum = 0;
        for (const v of heap.h) sum += v;
        ans.push([id, Math.floor(sum / 5)]);
    }
    return ans;
}