Kth Smallest Number in M Sorted Lists

int kthSmallest(vector<vector<int>>& lists, int k) {
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
    for (int i = 0; i < (int)lists.size(); ++i)
        if (!lists[i].empty()) pq.emplace(lists[i][0], i, 0);
    while (--k > 0) {
        auto [v, li, ii] = pq.top(); pq.pop();
        if (ii + 1 < (int)lists[li].size())
            pq.emplace(lists[li][ii + 1], li, ii + 1);
    }
    return get<0>(pq.top());
}

import "container/heap"

type entry struct{ v, li, ii int }
type minEntryHeap []entry

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

func kthSmallest(lists [][]int, k int) int {
    pq := &minEntryHeap{}
    for i, list := range lists {
        if len(list) > 0 {
            heap.Push(pq, entry{list[0], i, 0})
        }
    }
    for ; k > 1; k-- {
        e := heap.Pop(pq).(entry)
        if e.ii+1 < len(lists[e.li]) {
            heap.Push(pq, entry{lists[e.li][e.ii+1], e.li, e.ii + 1})
        }
    }
    return (*pq)[0].v
}

import heapq
from typing import List

class Solution:
    def kthSmallest(self, lists: List[List[int]], k: int) -> int:
        pq = []
        for i, lst in enumerate(lists):
            if lst:
                heapq.heappush(pq, (lst[0], i, 0))
        while k > 1:
            v, li, ii = heapq.heappop(pq)
            if ii + 1 < len(lists[li]):
                heapq.heappush(pq, (lists[li][ii + 1], li, ii + 1))
            k -= 1
        return pq[0][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][0] > this.h[i][0]) { [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][0] < this.h[best][0]) best = l;
                if (r < n && this.h[r][0] < this.h[best][0]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

function kthSmallest(lists, k) {
    const pq = new MinHeap();
    for (let i = 0; i < lists.length; i++) {
        if (lists[i].length) pq.push([lists[i][0], i, 0]);
    }
    while (--k > 0) {
        const [v, li, ii] = pq.pop();
        if (ii + 1 < lists[li].length) {
            pq.push([lists[li][ii + 1], li, ii + 1]);
        }
    }
    return pq.top()[0];
}

class Solution {
    public int kthSmallest(int[][] lists, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i].length > 0) pq.offer(new int[]{lists[i][0], i, 0});
        }
        while (k > 1) {
            int[] e = pq.poll();
            int li = e[1], ii = e[2];
            if (ii + 1 < lists[li].length) {
                pq.offer(new int[]{lists[li][ii + 1], li, ii + 1});
            }
            k--;
        }
        return pq.peek()[0];
    }
}

type Entry = [number, number, number]; // [value, listIdx, idxInList]

class MinHeap {
    private h: Entry[] = [];
    size(): number { return this.h.length; }
    top(): Entry { return this.h[0]; }
    push(v: Entry): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] > this.h[i][0]) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
            else break;
        }
    }
    pop(): Entry {
        const top = this.h[0];
        const last = this.h.pop() as Entry;
        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][0] < this.h[best][0]) best = l;
                if (r < n && this.h[r][0] < this.h[best][0]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
}

function kthSmallest(lists: number[][], k: number): number {
    const pq = new MinHeap();
    for (let i = 0; i < lists.length; i++) {
        if (lists[i].length) pq.push([lists[i][0], i, 0]);
    }
    while (--k > 0) {
        const [, li, ii] = pq.pop();
        if (ii + 1 < lists[li].length) {
            pq.push([lists[li][ii + 1], li, ii + 1]);
        }
    }
    return pq.top()[0];
}