The k-th largest value

import heapq

def kth_largest(nums, k):
    heap = []                          # the k largest so far; heap[0] is the weakest of them
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)     # pop the weakest and push x in one O(log k) step
    return heap[0]

#include <vector>
#include <queue>
#include <functional>

int solve(const std::vector<int>& nums, int k) {
    // std::greater makes priority_queue a min-heap: top() is the weakest of the k largest
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    for (int x : nums) {
        if (static_cast<int>(heap.size()) < k) heap.push(x);
        else if (x > heap.top()) { heap.pop(); heap.push(x); }
    }
    return heap.top();
}

class Solution {
    public int kthLargest(int[] nums, int k) {
        java.util.PriorityQueue<Integer> heap = new java.util.PriorityQueue<>();   // min-heap
        for (int x : nums) {
            if (heap.size() < k) heap.add(x);
            else if (x > heap.peek()) { heap.poll(); heap.add(x); }
        }
        return heap.peek();
    }
}

function kthLargest(nums, k) {
  const h = [];                        // binary min-heap of the k largest so far
  const up = i => {
    while (i > 0) { const p = (i - 1) >> 1; if (h[p] <= h[i]) break; [h[p], h[i]] = [h[i], h[p]]; i = p; }
  };
  const down = i => {
    for (;;) {
      const l = 2 * i + 1, r = l + 1; let m = i;
      if (l < h.length && h[l] < h[m]) m = l;
      if (r < h.length && h[r] < h[m]) m = r;
      if (m === i) return;
      [h[m], h[i]] = [h[i], h[m]]; i = m;
    }
  };
  for (const x of nums) {
    if (h.length < k) { h.push(x); up(h.length - 1); }
    else if (x > h[0]) { h[0] = x; down(0); }   // replace the weakest in place
  }
  return h[0];
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn solve(nums: &[i64], k: usize) -> i64 {
    // BinaryHeap is a max-heap; Reverse makes it a min-heap of the k largest
    let mut heap = BinaryHeap::with_capacity(k + 1);
    for &x in nums {
        if heap.len() < k {
            heap.push(Reverse(x));
        } else if x > heap.peek().unwrap().0 {
            heap.pop();
            heap.push(Reverse(x));
        }
    }
    heap.peek().unwrap().0
}

import qualified Data.Map.Strict as M

-- A Map from value to count is a min-heap: findMin is the weakest of the k largest.
solve :: [Int] -> Int -> Int
solve nums k = fst (M.findMin heap)
  where
    (heap, _) = foldl step (M.empty, 0 :: Int) nums
    step (m, size) x
      | size < k              = (M.insertWith (+) x 1 m, size + 1)
      | x > fst (M.findMin m) = (M.insertWith (+) x 1 (dropMin m), size)
      | otherwise             = (m, size)
    dropMin m = case M.findMin m of
      (v, 1) -> M.delete v m
      (v, c) -> M.insert v (c - 1) m