Kopiec (binarny)
30.11.2009 - Michał Karpiński
Zmiana wartości i-tego węzłaZałóżmy, że chcemy zmienić wartość któregokolwiek z elementów kopca. Potrzebna nam będzie operacja CHANGE-VAL(A,i,k). Jest jednak pewne ograniczenie nałożone na nową wartość danego elementu. Ograniczenie to zależy od typu kopca: w przypadku kopca typu max wartość i-tego węzła możemy jedynie zwiększać, a w kopcu typu min zmniejszać. Dla przykładu weźmy kopiec typu max. Zauważmy, że jeżeli zwiększymy wartość i-tego węzła, to ten węzeł nadal spełnia własność kopca, natomiast gdybyśmy zmniejszyli wartość nie mielibyśmy tej pewności. Gdy już zwiększymy wartość w i-tym węźle to istnieje szansa, że rodzic tego węzła nie spełnia własności kopca, sprawdzamy wtedy, która z wartości jest większa i w razie potrzeby dokonujemy zamiany miejsc. W najgorszym przypadku porównujemy wartości rodzic-potomek dopóki nie znajdziemy się w korzeniu. Procedura CHANGE-VAL(A,i,k) działa w czasie O(log n) Dodawanie elementówPosiadając możliwość zmiany wartości i-tego węzła możemy łatwo stworzyć procedurę dodawania nowego elementu do kopca. Jedyne co trzeba zrobić to zwiększyć rozmiar kopca o 1, co spowoduje dodanie nowego ( pustego ) elementu na koniec kopca. Następnie zmieniamy wartość ostatniego elementu procedurą CHANGE-VAL(A, KOPIEC-SIZE( A ) ,k) , gdzie k jest wartością nowego elementu. Wiemy, że operacja zmiany wartości i-tego węzła działa w czasie O(log n), czyli tyle też zajmie procedura INSERT(A,x). Sprawdźmy jak INSERT(A,x) działa w praktyce: (4 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com