Algorytmy i struktury danych · Senior · Pytanie 41 z 75
Jaka jest złożoność budowania kopca binarnego z n nieposortowanych elementów przesiewaniem w dół (heapify)?
- ✓Poprawna odpowiedź: O(n)
- 2O(log n)
- 3O(n log n)
Wyjaśnienie
Większość węzłów jest blisko dołu i przesiewa się tylko trochę: połowa węzłów przesuwa się o 0 poziomów, ćwierć o 1 i tak dalej. Suma zbiega do O(n). Wstawianie elementów po jednym dałoby O(n log n).