Алгоритми та структури даних · Middle · Запитання 11 з 75
Як ефективно знайти k найбільших елементів великого масиву?
- ✓Правильна відповідь: Тримати min-купу розміром k і заміняти корінь, коли трапляється більше значення
- 2Покласти всі елементи в
Setі взяти перші k - 3Щоразу при надходженні значення сортувати весь масив за спаданням
Пояснення
Купа завжди містить k найбільших із побачених, а її корінь - найменший серед них. Загальна вартість O(n log k), що краще за сортування (O(n log n)) для малих k, і працює навіть на потоках.