ハッシュとヒープで出てくる回数の多い値を k 個選ぶ

from collections import Counter
from heapq import heappush
from heapq import heappop


def top_k_frequent(nums, k):
    count = Counter(nums)
    heap = []
    for v, c in count.items():
        heappush(heap, (c, -v))
        if len(heap) > k:
            heappop(heap)
    out = []
    while heap:
        c, v = heappop(heap)
        out.append(-v)
    return out[::-1]

function topKFrequent(nums, k) {
  const count = new Map();
  for (const x of nums) {
    const c = count.get(x) ?? 0;
    count.set(x, c + 1);
  }
  const h = [];
  for (const [v, c] of count) {
    push(h, [c, v]);
    if (h.length > k) {
      pop(h);
    }
  }
  const out = [];
  while (h.length > 0) {
    out.push(pop(h)[1]);
  }
  return out.reverse();
}

function less(a, b) {
  if (a[0] !== b[0]) {
    return a[0] < b[0];
  }
  return a[1] > b[1];
}

function push(h, x) {
  h.push(x);
  let i = h.length - 1;
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (!less(h[i], h[p])) {
      return;
    }
    [h[p], h[i]] = [h[i], h[p]];
    i = p;
  }
}

function pop(h) {
  const top = h[0];
  const last = h.pop();
  const n = h.length;
  if (n === 0) {
    return top;
  }
  h[0] = last;
  const lt = (a, b) =>
    less(h[a], h[b]);
  let i = 0;
  while (true) {
    let s = i;
    const l = 2 * i + 1;
    const r = l + 1;
    if (l < n && lt(l, s)) {
      s = l;
    }
    if (r < n && lt(r, s)) {
      s = r;
    }
    if (s === i) {
      return top;
    }
    [h[s], h[i]] = [h[i], h[s]];
    i = s;
  }
}

import "container/heap"

type pair struct {
	c, v int
}

type pairs []pair

func (h pairs) Len() int {
	return len(h)
}

func (h pairs) Less(
	i, j int,
) bool {
	if h[i].c != h[j].c {
		return h[i].c < h[j].c
	}
	return h[i].v > h[j].v
}

func (h pairs) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *pairs) Push(x any) {
	*h = append(*h, x.(pair))
}

func (h *pairs) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func topKFrequent(
	nums []int, k int,
) []int {
	count := map[int]int{}
	for _, x := range nums {
		count[x]++
	}
	h := &pairs{}
	for v, c := range count {
		heap.Push(h, pair{c, v})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	n := h.Len()
	out := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		p := heap.Pop(h).(pair)
		out[i] = p.v
	}
	return out
}