Algorytmy i struktury danych · Senior · Pytanie 74 z 75
Czego sztuczka „dwóch kopców” nie obsługuje wydajnie w porównaniu ze zbalansowanym BST?
- ✓Poprawna odpowiedź: Usuwania dowolnego elementu ze środka
- 2Odczytu bieżącej mediany w O(1)
- 3Wstawiania nowego elementu w O(log n)
Wyjaśnienie
Kopce tanio usuwają tylko korzeń. Do mediany w przesuwanym oknie potrzebne jest leniwe usuwanie (oznaczanie usuniętych wartości i pomijanie ich później) albo uporządkowany multizbiór, np. zbalansowane drzewo, które usuwa dowolną wartość w O(log n).