Gegeven is een lange lijst (of een groot bestand) met getallen (bv. een biljard gehele getallen). Gevraagd is om uit deze lijst de \(k\) grootste getallen te bepalen, waarbij \(k\) een klein natuurlijk getal is. Schrijf hiervoor een efficiënt algoritme dat gebruik maakt van een prioriteitswachtlijn.

Opgave

Schrijf een Python-functie topK(lijst:list,k:int). Deze functie krijgt een lijst van lengte \(n\) en een getal \(k\) als parameters. De functie moet de \(k\) grootste elementen uit lijst gesorteerd teruggeven. Deze functie mag een tijdscomplexiteit van maximaal \(\Theta(n \, \log k)\) hebben.

Voorbeelden

>>> topK([1,5,7,7,5,4,2,3,6,9,9,1,12,3,21,5,4,1,2,36,5,4,1,2,3,6,54,6,8,5,2,6,5,1,5,8,5,10,1,2,5,4,8,2,5,12],10)
[8, 8, 9, 9, 10, 12, 12, 21, 36, 54]
>>> topK([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],10)
[6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> topK([15,14,13,12,11,10,9,8,7,6,5,4,3,2,1],10)
[6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> topK([1,5,5,7,5,3,5,8,6,9],10)
[1, 3, 5, 5, 5, 5, 6, 7, 8, 9]