Merge K Sorted Lists

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b){ return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        for (auto h : lists) if (h) pq.push(h);
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (!pq.empty()) {
            ListNode* top = pq.top(); pq.pop();
            tail->next = top;
            tail = top;
            if (top->next) pq.push(top->next);
        }
        return dummy.next;
    }
};

import "container/heap"

type nodeHeap []*ListNode

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

func mergeKLists(lists []*ListNode) *ListNode {
    pq := &nodeHeap{}
    for _, h := range lists {
        if h != nil {
            *pq = append(*pq, h)
        }
    }
    heap.Init(pq)
    dummy := &ListNode{}
    tail := dummy
    for pq.Len() > 0 {
        top := heap.Pop(pq).(*ListNode)
        tail.Next = top
        tail = top
        if top.Next != nil {
            heap.Push(pq, top.Next)
        }
    }
    return dummy.Next
}

import heapq
from typing import List, Optional

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        pq: List[tuple] = []
        for i, h in enumerate(lists):
            if h:
                heapq.heappush(pq, (h.val, i, h))
        dummy = ListNode(0)
        tail = dummy
        while pq:
            _, i, node = heapq.heappop(pq)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(pq, (node.next.val, i, node.next))
        return dummy.next

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

function mergeKLists(lists) {
    const pq = new MinHeap((a, b) => a.val - b.val);
    for (const h of lists) if (h) pq.push(h);
    const dummy = new ListNode(0);
    let tail = dummy;
    while (pq.size() > 0) {
        const top = pq.pop();
        tail.next = top;
        tail = top;
        if (top.next) pq.push(top.next);
    }
    return dummy.next;
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode h : lists) if (h != null) pq.offer(h);
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!pq.isEmpty()) {
            ListNode top = pq.poll();
            tail.next = top;
            tail = top;
            if (top.next != null) pq.offer(top.next);
        }
        return dummy.next;
    }
}

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

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    const pq = new MinHeap<ListNode>((a, b) => a.val - b.val);
    for (const h of lists) if (h) pq.push(h);
    const dummy = new ListNode(0);
    let tail: ListNode = dummy;
    while (pq.size() > 0) {
        const top = pq.pop();
        tail.next = top;
        tail = top;
        if (top.next) pq.push(top.next);
    }
    return dummy.next;
}