Kth Largest Element in a Stream

class KthLargest {
    priority_queue<int, vector<int>, greater<int>> pq;
    int k;
public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }
    int add(int v) {
        pq.push(v);
        if ((int)pq.size() > k) pq.pop();
        return pq.top();
    }
};

import "container/heap"

type minIntHeap []int

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

type KthLargest struct {
    pq *minIntHeap
    k  int
}

func Constructor(k int, nums []int) KthLargest {
    obj := KthLargest{pq: &minIntHeap{}, k: k}
    for _, v := range nums {
        obj.Add(v)
    }
    return obj
}

func (kl *KthLargest) Add(val int) int {
    heap.Push(kl.pq, val)
    if kl.pq.Len() > kl.k {
        heap.Pop(kl.pq)
    }
    return (*kl.pq)[0]
}

from typing import List
import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.pq: List[int] = []
        for v in nums:
            self.add(v)

    def add(self, val: int) -> int:
        heapq.heappush(self.pq, val)
        if len(self.pq) > self.k:
            heapq.heappop(self.pq)
        return self.pq[0]

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    top() { return this.h[0]; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] > this.h[i]) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
            else break;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0, n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l] < this.h[best]) best = l;
                if (r < n && this.h[r] < this.h[best]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

class KthLargest {
    constructor(k, nums) {
        this.k = k;
        this.pq = new MinHeap();
        for (const v of nums) this.add(v);
    }
    add(val) {
        this.pq.push(val);
        if (this.pq.size() > this.k) this.pq.pop();
        return this.pq.top();
    }
}

class KthLargest {
    private PriorityQueue<Integer> pq = new PriorityQueue<>();
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int v : nums) add(v);
    }

    public int add(int val) {
        pq.offer(val);
        if (pq.size() > k) pq.poll();
        return pq.peek();
    }
}

class MinHeap {
    private h: number[] = [];
    size(): number { return this.h.length; }
    top(): number { return this.h[0]; }
    push(v: number): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] > this.h[i]) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
            else break;
        }
    }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l] < this.h[best]) best = l;
                if (r < n && this.h[r] < this.h[best]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

class KthLargest {
    private k: number;
    private pq: MinHeap;

    constructor(k: number, nums: number[]) {
        this.k = k;
        this.pq = new MinHeap();
        for (const v of nums) this.add(v);
    }

    add(val: number): number {
        this.pq.push(val);
        if (this.pq.size() > this.k) this.pq.pop();
        return this.pq.top();
    }
}