Minimum Cost to Connect Sticks

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int, vector<int>, greater<int>> pq(sticks.begin(), sticks.end());
        int total = 0;
        while (pq.size() > 1) {
            int a = pq.top(); pq.pop();
            int b = pq.top(); pq.pop();
            total += a + b;
            pq.push(a + b);
        }
        return total;
    }
};

type intMinHeap []int

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

func connectSticks(sticks []int) int {
    h := intMinHeap(append([]int(nil), sticks...))
    heap.Init(&h)
    total := 0
    for h.Len() > 1 {
        a := heap.Pop(&h).(int)
        b := heap.Pop(&h).(int)
        total += a + b
        heap.Push(&h, a+b)
    }
    return total
}

from typing import List
import heapq

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        heap = sticks[:]
        heapq.heapify(heap)
        total = 0
        while len(heap) > 1:
            a = heapq.heappop(heap)
            b = heapq.heappop(heap)
            total += a + b
            heapq.heappush(heap, a + b)
        return total

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

function connectSticks(sticks) {
    const heap = new MinHeap(sticks);
    let total = 0;
    while (heap.size() > 1) {
        const a = heap.pop();
        const b = heap.pop();
        total += a + b;
        heap.push(a + b);
    }
    return total;
}

class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int s : sticks) pq.offer(s);
        int total = 0;
        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            total += a + b;
            pq.offer(a + b);
        }
        return total;
    }
}

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

function connectSticks(sticks: number[]): number {
    const heap = new MinHeap(sticks);
    let total = 0;
    while (heap.size() > 1) {
        const a = heap.pop();
        const b = heap.pop();
        total += a + b;
        heap.push(a + b);
    }
    return total;
}