Kopiec (binarny)

30.11.2009 - Michał Karpiński
Trudność

Zmiana wartości i-tego węzła

Załóż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ów

Posiadają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:

5
Twoja ocena: Brak Ocena: 5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com