Алгоритми та структури даних · Senior · Запитання 41 з 75
Яка складність побудови бінарної купи з n невідсортованих елементів просіюванням униз (heapify)?
- ✓Правильна відповідь: O(n)
- 2O(log n)
- 3O(n log n)
Пояснення
Більшість вузлів біля низу й просіюється зовсім трохи: половина вузлів зсувається на 0 рівнів, чверть на 1 і так далі. Сума збігається до O(n). Вставка елементів по одному дала б O(n log n).