Heaps

val heap = PriorityQueue<Int>()          // min-heap by default
listOf(5, 1, 8, 3).forEach { heap.add(it) }
println(heap.peek())                     // 1: peek at the smallest
println(heap.poll())                     // 1: remove it

val maxHeap = PriorityQueue<Int>(compareByDescending { it })   // or reverseOrder()

PriorityQueue<Integer> heap = new PriorityQueue<>();       // min-heap by default
for (int value : List.of(5, 1, 8, 3)) heap.add(value);
System.out.println(heap.peek());                           // 1: peek at the smallest
System.out.println(heap.poll());                           // 1: remove it

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// No built-in heap: a small binary heap with a comparator (or a package)
class Heap<T> {
  private readonly items: T[] = [];
  constructor(private readonly before: (a: T, b: T) => boolean) {}   // true if a belongs above b

  get size() { return this.items.length; }
  get unordered(): readonly T[] { return this.items; }               // the backing array, heap order
  peek(): T | undefined { return this.items[0]; }

  push(value: T) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {                                                  // sift up
      const parent = (i - 1) >> 1;
      if (!this.before(a[i], a[parent])) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
  }

  pop(): T | undefined {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0 && last !== undefined) {
      a[0] = last;
      let i = 0;
      while (true) {                                                 // sift down
        const l = 2 * i + 1;
        const r = l + 1;
        let best = i;
        if (l < a.length && this.before(a[l], a[best])) best = l;
        if (r < a.length && this.before(a[r], a[best])) best = r;
        if (best === i) break;
        [a[i], a[best]] = [a[best], a[i]];
        i = best;
      }
    }
    return top;
  }
}

const heap = new Heap<number>((a, b) => a < b);      // a min-heap
for (const value of [5, 1, 8, 3]) heap.push(value);
console.log(heap.peek());                            // 1: peek at the smallest
console.log(heap.pop());                             // 1: remove it

const maxHeap = new Heap<number>((a, b) => a > b);

fun findKthLargest(nums: IntArray, k: Int): Int {
    val heap = PriorityQueue<Int>()
    for (n in nums) {
        heap.add(n)
        if (heap.size > k) heap.poll()             // drop the smallest: it can't be in the top k
    }
    return heap.peek()
}

int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int n : nums) {
        heap.add(n);
        if (heap.size() > k) heap.poll();          // drop the smallest: it can't be in the top k
    }
    return heap.peek();
}

function findKthLargest(nums: number[], k: number): number {
  const heap = new Heap<number>((a, b) => a < b);   // min-heap
  for (const n of nums) {
    heap.push(n);
    if (heap.size > k) heap.pop();                  // drop the smallest: it can't be in the top k
  }
  return heap.peek()!;
}

fun mergeSorted(lists: List<IntArray>): List<Int> {
    // Triple(value, listIndex, elementIndex), ordered by value
    val heap = PriorityQueue<Triple<Int, Int, Int>>(compareBy { it.first })
    lists.forEachIndexed { i, list -> if (list.isNotEmpty()) heap.add(Triple(list[0], i, 0)) }
    val merged = mutableListOf<Int>()
    while (heap.isNotEmpty()) {
        val (value, list, index) = heap.poll()
        merged += value
        if (index + 1 < lists[list].size) heap.add(Triple(lists[list][index + 1], list, index + 1))
    }
    return merged
}

static List<Integer> mergeSorted(List<int[]> lists) {
    // int[] {value, listIndex, elementIndex}, ordered by value
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));
    for (int i = 0; i < lists.size(); i++) {
        if (lists.get(i).length > 0) heap.add(new int[] {lists.get(i)[0], i, 0});
    }
    List<Integer> merged = new ArrayList<>();
    while (!heap.isEmpty()) {
        int[] e = heap.poll();
        merged.add(e[0]);
        int[] list = lists.get(e[1]);
        if (e[2] + 1 < list.length) heap.add(new int[] {list[e[2] + 1], e[1], e[2] + 1});
    }
    return merged;
}

function mergeSorted(lists: number[][]): number[] {
  // [value, listIndex, elementIndex], ordered by value
  const heap = new Heap<[number, number, number]>((a, b) => a[0] < b[0]);
  lists.forEach((list, i) => { if (list.length > 0) heap.push([list[0], i, 0]); });
  const merged: number[] = [];
  while (heap.size > 0) {
    const [value, list, index] = heap.pop()!;
    merged.push(value);
    if (index + 1 < lists[list].length) heap.push([lists[list][index + 1], list, index + 1]);
  }
  return merged;
}