Fernando Nathaniel Sutanto
2106629995

import heapq
def RetrieveTopK(a, m, l, r, k):
    ans = []
    heap = []
    heapq.heappush(heap, (a[m[l][r]], l, r))  #Top 1
    while len(ans) < k and len(heap) > 0:
        element, left, right = heapq.heappop(heap)
        ans.append(element)

        position = m[left][right]
        if left <= position - 1:
            heapq.heappush(heap, (a[m[left][position-1]], left, position-1))  #the maxi from left part
        if position + 1 <= right:
            heapq.heappush(heap, (a[m[position+1][right]], position+1, right))  #the maxi from right part
    return ans

Algoritma di atas bekerja dengan bantuan heap. Heap berisikan kumpulan-kumpulan kandidat Top K pada subarray tsb. Pada awalnya yang dipush hanyalah yang terbesar dari range tsb lalu secara logika kandidat selanjutnya adalah terbesar dari bagian kiri nya elemen terbesar dan terbesar dari bagian kanan nya elemen terbesar. Algoritma dilakukan terus menerus selama masih belom mendapatkan K terbesar. Algoritma ini bisa dibilang bermetode divide and conquer.

Kompleksitas algoritma di atas adalah O(K log M) karena setiap iterasi kita berhasil menambahkan yang terbesar di heap ke jawaban maka untuk mendapatkan K terbesar membutuhkan K iterasi. Lalu pada masing-masing iterasi terdapat operasi pop, dan push. Karena kita memakai bantuan heap, masing-masing operasinya berjalan dengan O(log M). Jadi didapat kompleksitas O(K log M)