K-th Smallest Prime Fraction

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        int n = arr.size();
        auto cmp = [&](const pair<int,int>& a, const pair<int,int>& b){
            return (long long)arr[a.first] * arr[b.second] > (long long)arr[b.first] * arr[a.second];
        };
        priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
        for (int j = 1; j < n; ++j) pq.push({0, j});
        while (--k > 0) {
            auto [i, j] = pq.top(); pq.pop();
            if (i + 1 < j) pq.push({i + 1, j});
        }
        auto [i, j] = pq.top();
        return {arr[i], arr[j]};
    }
};

import "container/heap"

type fracHeap struct {
    pairs [][2]int
    arr   []int
}

func (h fracHeap) Len() int { return len(h.pairs) }
func (h fracHeap) Less(i, j int) bool {
    a, b := h.pairs[i], h.pairs[j]
    return h.arr[a[0]]*h.arr[b[1]] < h.arr[b[0]]*h.arr[a[1]]
}
func (h fracHeap) Swap(i, j int)       { h.pairs[i], h.pairs[j] = h.pairs[j], h.pairs[i] }
func (h *fracHeap) Push(x interface{}) { h.pairs = append(h.pairs, x.([2]int)) }
func (h *fracHeap) Pop() interface{} {
    n := len(h.pairs)
    x := h.pairs[n-1]
    h.pairs = h.pairs[:n-1]
    return x
}

func kthSmallestPrimeFraction(arr []int, k int) []int {
    n := len(arr)
    h := &fracHeap{arr: arr}
    for j := 1; j < n; j++ {
        heap.Push(h, [2]int{0, j})
    }
    for ; k > 1; k-- {
        p := heap.Pop(h).([2]int)
        if p[0]+1 < p[1] {
            heap.Push(h, [2]int{p[0] + 1, p[1]})
        }
    }
    top := h.pairs[0]
    return []int{arr[top[0]], arr[top[1]]}
}

from typing import List
import heapq

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        # heap entry: (value, i, j) where value = arr[i] / arr[j]
        pq: List = [(arr[0] / arr[j], 0, j) for j in range(1, n)]
        heapq.heapify(pq)
        for _ in range(k - 1):
            _, i, j = heapq.heappop(pq)
            if i + 1 < j:
                heapq.heappush(pq, (arr[i + 1] / arr[j], i + 1, j))
        _, i, j = pq[0]
        return [arr[i], arr[j]]

class MinHeap {
    constructor(cmp) { this.h = []; this.cmp = cmp; }
    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.cmp(this.h[i], this.h[p]) < 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.cmp(this.h[l], this.h[best]) < 0) best = l;
                if (r < n && this.cmp(this.h[r], 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 kthSmallestPrimeFraction(arr, k) {
    const n = arr.length;
    const pq = new MinHeap((a, b) => arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]);
    for (let j = 1; j < n; j++) pq.push([0, j]);
    while (--k > 0) {
        const [i, j] = pq.pop();
        if (i + 1 < j) pq.push([i + 1, j]);
    }
    const [i, j] = pq.top();
    return [arr[i], arr[j]];
}

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]
        );
        for (int j = 1; j < n; j++) pq.offer(new int[]{0, j});
        while (--k > 0) {
            int[] p = pq.poll();
            int i = p[0], j = p[1];
            if (i + 1 < j) pq.offer(new int[]{i + 1, j});
        }
        int[] top = pq.peek();
        return new int[]{arr[top[0]], arr[top[1]]};
    }
}

class MinHeap<T> {
    private h: T[] = [];
    constructor(private cmp: (a: T, b: T) => number) {}
    size(): number { return this.h.length; }
    top(): T { return this.h[0]; }
    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[i], this.h[p]) < 0) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; }
            else break;
        }
    }
    pop(): T {
        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.cmp(this.h[l], this.h[best]) < 0) best = l;
                if (r < n && this.cmp(this.h[r], 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 kthSmallestPrimeFraction(arr: number[], k: number): number[] {
    const n = arr.length;
    const pq = new MinHeap<[number, number]>((a, b) => arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]);
    for (let j = 1; j < n; j++) pq.push([0, j]);
    while (--k > 0) {
        const [i, j] = pq.pop();
        if (i + 1 < j) pq.push([i + 1, j]);
    }
    const [i, j] = pq.top();
    return [arr[i], arr[j]];
}