ヒープで k 番目に大きい値を求める

from heapq import heappush
from heapq import heapreplace


def kth_largest(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heappush(heap, x)
        elif x > heap[0]:
            heapreplace(heap, x)
    return heap[0]

function kthLargest(nums, k) {
  const h = [];
  for (const x of nums) {
    if (h.length < k) {
      h.push(x);
      up(h, h.length - 1);
    } else if (x > h[0]) {
      h[0] = x;
      down(h, 0);
    }
  }
  return h[0];
}

function up(h, i) {
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (h[p] <= h[i]) {
      return;
    }
    [h[p], h[i]] = [h[i], h[p]];
    i = p;
  }
}

function down(h, i) {
  const n = h.length;
  while (true) {
    let s = i;
    const l = 2 * i + 1;
    const r = l + 1;
    if (l < n && h[l] < h[s]) {
      s = l;
    }
    if (r < n && h[r] < h[s]) {
      s = r;
    }
    if (s === i) {
      return;
    }
    [h[s], h[i]] = [h[i], h[s]];
    i = s;
  }
}

import "container/heap"

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 any) {
	*h = append(*h, x.(int))
}

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

func kthLargest(
	nums []int, k int,
) int {
	h := &minHeap{}
	for _, x := range nums {
		if h.Len() < k {
			heap.Push(h, x)
		} else if x > (*h)[0] {
			(*h)[0] = x
			heap.Fix(h, 0)
		}
	}
	return (*h)[0]
}