Heaps & Priority Queues

import heapq


def find_kth_largest(nums: list[int], k: int) -> int:
    """The kth largest value in `nums`, counting duplicates."""
    heap: list[int] = []  # The k largest values seen so far.
    for num in nums:
        heapq.heappush(heap, num)
        # Evict the smallest: k values at least as big sit above it, so it's out of the top k.
        if len(heap) > k:
            heapq.heappop(heap)
    # The weakest member of the top k is the kth largest.
    return heap[0]


if __name__ == "__main__":
    print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5
    print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))  # 4
    print(find_kth_largest([-1, 2, 0], 3))  # -1

// The kth largest value in `nums`, counting duplicates.
export function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap(); // The k largest values seen so far.
  for (const num of nums) {
    heap.push(num);
    // Evict the smallest: k values at least as big sit above it, so it's out of the top k.
    if (heap.size() > k) heap.pop();
  }
  // The weakest member of the top k is the kth largest.
  return heap.peek();
}

// TypeScript has no built-in heap, so this is the template's min-heap, trimmed.
class MinHeap {
  private items: number[] = [];

  size(): number {
    return this.items.length;
  }

  peek(): number {
    return this.items[0];
  }

  push(value: number): void {
    const items = this.items;
    items.push(value);
    let i = items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (items[parent] <= items[i]) break;
      [items[i], items[parent]] = [items[parent], items[i]];
      i = parent;
    }
  }

  pop(): number {
    const items = this.items;
    const top = items[0];
    [items[0], items[items.length - 1]] = [items[items.length - 1], items[0]];
    items.pop();
    let i = 0;
    while (true) {
      let smallest = i;
      for (const child of [2 * i + 1, 2 * i + 2]) {
        if (child < items.length && items[child] < items[smallest]) smallest = child;
      }
      if (smallest === i) break;
      [items[i], items[smallest]] = [items[smallest], items[i]];
      i = smallest;
    }
    return top;
  }
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4
console.log(findKthLargest([-1, 2, 0], 3)); // -1

package main

import (
	"container/heap"
	"fmt"
)

// intHeap is a min-heap of ints. container/heap does the sifting; you supply
// the storage through these five methods.
type intHeap []int

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

// findKthLargest returns the kth largest value in nums, counting duplicates.
func findKthLargest(nums []int, k int) int {
	h := &intHeap{} // The k largest values seen so far.
	for _, num := range nums {
		heap.Push(h, num)
		// Evict the smallest: k values at least as big sit above it, so it's out of the top k.
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	// The weakest member of the top k is the kth largest.
	return (*h)[0]
}

func main() {
	fmt.Println(findKthLargest([]int{3, 2, 1, 5, 6, 4}, 2))          // 5
	fmt.Println(findKthLargest([]int{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4)) // 4
	fmt.Println(findKthLargest([]int{-1, 2, 0}, 3))                  // -1
}

using System;
using System.Collections.Generic;

public class Solution
{
    // The kth largest value in nums, counting duplicates.
    public static int FindKthLargest(int[] nums, int k)
    {
        var heap = new PriorityQueue<int, int>(); // The k largest values seen so far.
        foreach (int num in nums)
        {
            heap.Enqueue(num, num); // Each value is its own priority.
            // Evict the smallest: k values at least as big sit above it, so it's out of the top k.
            if (heap.Count > k) heap.Dequeue();
        }
        // The weakest member of the top k is the kth largest.
        return heap.Peek();
    }

    public static void Main()
    {
        Console.WriteLine(FindKthLargest(new[] { 3, 2, 1, 5, 6, 4 }, 2)); // 5
        Console.WriteLine(FindKthLargest(new[] { 3, 2, 3, 1, 2, 4, 5, 5, 6 }, 4)); // 4
        Console.WriteLine(FindKthLargest(new[] { -1, 2, 0 }, 3)); // -1
    }
}

import java.util.PriorityQueue;

public class Solution {
    // The kth largest value in nums, counting duplicates.
    static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // The k largest values seen so far.
        for (int num : nums) {
            heap.offer(num);
            // Evict the smallest: k values at least as big sit above it, so it's out of the top k.
            if (heap.size() > k) heap.poll();
        }
        // The weakest member of the top k is the kth largest.
        return heap.peek();
    }

    public static void main(String[] args) {
        System.out.println(findKthLargest(new int[] {3, 2, 1, 5, 6, 4}, 2)); // 5
        System.out.println(findKthLargest(new int[] {3, 2, 3, 1, 2, 4, 5, 5, 6}, 4)); // 4
        System.out.println(findKthLargest(new int[] {-1, 2, 0}, 3)); // -1
    }
}

import heapq


class MedianFinder:
    """Running median of a stream, kept in two heaps that split it in half."""

    def __init__(self) -> None:
        # Before Python 3.14, heapq only makes min-heaps, so low stores negated values.
        self.low: list[int] = []  # Max-heap of the smaller half.
        self.high: list[int] = []  # Min-heap of the larger half.

    def add_num(self, num: int) -> None:
        # Pass every number through low, so the biggest of the smaller half moves
        # up to high. That keeps everything in low <= everything in high.
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        # Rebalance so low holds as many values as high, or one more.
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def find_median(self) -> float:
        # Odd count: the middle value is the top of low.
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        # Even count: average the two middle values.
        return (-self.low[0] + self.high[0]) / 2


if __name__ == "__main__":
    # Prints 1.0 1.5 2.0, then 5.0 10.0 5.0 4.0 5.0, then -1.0 -1.5, one per line.
    for stream in [[1, 2, 3], [5, 15, 1, 3, 8], [-1, -2]]:
        finder = MedianFinder()
        for num in stream:
            finder.add_num(num)
            print(f"{finder.find_median():.1f}")

// Running median of a stream, kept in two heaps that split it in half.
export class MedianFinder {
  private low = new Heap((a, b) => a > b); // Max-heap of the smaller half.
  private high = new Heap((a, b) => a < b); // Min-heap of the larger half.

  addNum(num: number): void {
    // Pass every number through low, so the biggest of the smaller half moves
    // up to high. That keeps everything in low <= everything in high.
    this.low.push(num);
    this.high.push(this.low.pop());
    // Rebalance so low holds as many values as high, or one more.
    if (this.high.size() > this.low.size()) this.low.push(this.high.pop());
  }

  findMedian(): number {
    // Odd count: the middle value is the top of low.
    if (this.low.size() > this.high.size()) return this.low.peek();
    // Even count: average the two middle values.
    return (this.low.peek() + this.high.peek()) / 2;
  }
}

// TypeScript has no built-in heap. This one keeps the value for which
// before(value, other) holds at the top, so it works as a min- or max-heap.
class Heap {
  private items: number[] = [];
  private readonly before: (a: number, b: number) => boolean;

  constructor(before: (a: number, b: number) => boolean) {
    this.before = before;
  }

  size(): number {
    return this.items.length;
  }

  peek(): number {
    return this.items[0];
  }

  push(value: number): void {
    const items = this.items;
    items.push(value);
    let i = items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (!this.before(items[i], items[parent])) break;
      [items[i], items[parent]] = [items[parent], items[i]];
      i = parent;
    }
  }

  pop(): number {
    const items = this.items;
    const top = items[0];
    [items[0], items[items.length - 1]] = [items[items.length - 1], items[0]];
    items.pop();
    let i = 0;
    while (true) {
      let first = i;
      for (const child of [2 * i + 1, 2 * i + 2]) {
        if (child < items.length && this.before(items[child], items[first])) first = child;
      }
      if (first === i) break;
      [items[i], items[first]] = [items[first], items[i]];
      i = first;
    }
    return top;
  }
}

// Prints 1.0 1.5 2.0, then 5.0 10.0 5.0 4.0 5.0, then -1.0 -1.5, one per line.
for (const stream of [[1, 2, 3], [5, 15, 1, 3, 8], [-1, -2]]) {
  const finder = new MedianFinder();
  for (const num of stream) {
    finder.addNum(num);
    console.log(finder.findMedian().toFixed(1));
  }
}

package main

import (
	"container/heap"
	"fmt"
)

// intHeap is a min-heap of ints for container/heap.
type intHeap []int

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

// medianFinder keeps the running median of a stream in two heaps that split
// it in half. intHeap is a min-heap, so low stores negated values.
type medianFinder struct {
	low  intHeap // Max-heap of the smaller half.
	high intHeap // Min-heap of the larger half.
}

func (m *medianFinder) addNum(num int) {
	// Pass every number through low, so the biggest of the smaller half moves
	// up to high. That keeps everything in low <= everything in high.
	heap.Push(&m.low, -num)
	heap.Push(&m.high, -heap.Pop(&m.low).(int))
	// Rebalance so low holds as many values as high, or one more.
	if m.high.Len() > m.low.Len() {
		heap.Push(&m.low, -heap.Pop(&m.high).(int))
	}
}

func (m *medianFinder) findMedian() float64 {
	// Odd count: the middle value is the top of low.
	if m.low.Len() > m.high.Len() {
		return float64(-m.low[0])
	}
	// Even count: average the two middle values. Convert before dividing so
	// integer division doesn't drop the .5.
	return float64(-m.low[0]+m.high[0]) / 2
}

func main() {
	// Prints 1.0 1.5 2.0, then 5.0 10.0 5.0 4.0 5.0, then -1.0 -1.5, one per line.
	for _, stream := range [][]int{{1, 2, 3}, {5, 15, 1, 3, 8}, {-1, -2}} {
		finder := &medianFinder{}
		for _, num := range stream {
			finder.addNum(num)
			fmt.Printf("%.1f\n", finder.findMedian())
		}
	}
}

using System;
using System.Collections.Generic;
using System.Globalization;

public class Solution
{
    // Running median of a stream, kept in two heaps that split it in half.
    public class MedianFinder
    {
        // Max-heap of the smaller half: a reversed comparer puts the largest on top.
        readonly PriorityQueue<int, int> low = new(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        readonly PriorityQueue<int, int> high = new(); // Min-heap of the larger half.

        public void AddNum(int num)
        {
            // Pass every number through low, so the biggest of the smaller half moves
            // up to high. That keeps everything in low <= everything in high.
            low.Enqueue(num, num);
            int moved = low.Dequeue();
            high.Enqueue(moved, moved);
            // Rebalance so low holds as many values as high, or one more.
            if (high.Count > low.Count)
            {
                int back = high.Dequeue();
                low.Enqueue(back, back);
            }
        }

        public double FindMedian()
        {
            // Odd count: the middle value is the top of low.
            if (low.Count > high.Count) return low.Peek();
            // Even count: average the two middle values. Dividing by 2.0, not 2,
            // keeps the .5 that integer division would drop.
            return (low.Peek() + high.Peek()) / 2.0;
        }
    }

    public static void Main()
    {
        // Prints 1.0 1.5 2.0, then 5.0 10.0 5.0 4.0 5.0, then -1.0 -1.5, one per line.
        foreach (int[] stream in new[] { new[] { 1, 2, 3 }, new[] { 5, 15, 1, 3, 8 }, new[] { -1, -2 } })
        {
            var finder = new MedianFinder();
            foreach (int num in stream)
            {
                finder.AddNum(num);
                Console.WriteLine(finder.FindMedian().ToString("F1", CultureInfo.InvariantCulture));
            }
        }
    }
}

import java.util.Collections;
import java.util.Locale;
import java.util.PriorityQueue;

public class Solution {
    // Running median of a stream, kept in two heaps that split it in half.
    static class MedianFinder {
        // Max-heap of the smaller half: a reversed comparator puts the largest on top.
        private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
        private final PriorityQueue<Integer> high = new PriorityQueue<>(); // Min-heap of the larger half.

        void addNum(int num) {
            // Pass every number through low, so the biggest of the smaller half moves
            // up to high. That keeps everything in low <= everything in high.
            low.offer(num);
            high.offer(low.poll());
            // Rebalance so low holds as many values as high, or one more.
            if (high.size() > low.size()) low.offer(high.poll());
        }

        double findMedian() {
            // Odd count: the middle value is the top of low.
            if (low.size() > high.size()) return low.peek();
            // Even count: average the two middle values. Dividing by 2.0, not 2,
            // keeps the .5 that integer division would drop.
            return (low.peek() + high.peek()) / 2.0;
        }
    }

    public static void main(String[] args) {
        // Prints 1.0 1.5 2.0, then 5.0 10.0 5.0 4.0 5.0, then -1.0 -1.5, one per line.
        for (int[] stream : new int[][] {{1, 2, 3}, {5, 15, 1, 3, 8}, {-1, -2}}) {
            MedianFinder finder = new MedianFinder();
            for (int num : stream) {
                finder.addNum(num);
                System.out.println(String.format(Locale.ROOT, "%.1f", finder.findMedian()));
            }
        }
    }
}