786 - heap

class Solution:
    def kthSmallestPrimeFraction(self, A: List[int], K: int) -> List[int]:
        n = len(A)
        h = [(A[p]/A[n-1], p, n-1) for p in range(n-1)]
        heapq.heapify(h)

        while K:
            _, p, q = heapq.heappop(h)
            if p < q - 1:
                heapq.heappush(h, (A[p]/A[q-1], p, q - 1))
            K -= 1

        return [A[p], A[q]]