Algorytmy i struktury danych · Middle · Pytanie 11 z 75
Jak wydajnie znaleźć k największych elementów dużej tablicy?
- ✓Poprawna odpowiedź: Trzymać min-kopiec rozmiaru k i wymieniać korzeń, gdy pojawi się większa wartość
- 2Włożyć wszystkie elementy do
Seti wziąć pierwsze k - 3Sortować całą tablicę malejąco za każdym razem, gdy przyjdzie wartość
Wyjaśnienie
Kopiec zawsze zawiera k największych z dotąd widzianych, a jego korzeń jest najmniejszym z nich. Łączny koszt to O(n log k), lepiej niż sortowanie (O(n log n)) dla małego k, i działa także na strumieniach.