Kopiec (binarny)

30.11.2009 - Michał Karpiński
Trudność

Kopcowanie, czyli przywracanie własności kopca

W tym rozdziale zajmiemy się ważną procedurą do manipulowania kopcami. Przywracanie własności kopca jest podstawą do wykonywania innych operacji np. budowania kopca lub dodawania/usuwania pierwszego węzła.

Procedurę KOPCUJ(A,i) wywołujemy dla węzła o indeksie i znajdującego się w kopcu A. Dlaczego w nazwie procedury znajduje się słowo „przywracanie”? Ponieważ wywołując naszą procedurę zakładamy, że wszystkie węzły w kopcu oprócz i-tego spełniają własność kopca. Innymi słowy: żeby przywrócić własność całego kopca, należy przywrócić własność tylko dla i-tego węzła.

Zastanówmy się, jak powinna wyglądać procedura KOPCUJ(A,i). Myślę, że najlepiej będzie jeśli posłużymy się przykładem. Weźmy kopiec typu max w którym węzeł o indeksie 2 nie spełnia własności kopca. Taki kopiec mógłby wyglądać następująco:

A[i] - wartość węzła o indeksie i w kopcu A

Widać, że węzeł 2 nie spełnia własności kopca zarówno względem lewego jak i prawego potomka. W tym momencie mamy dwie możliwości: zamienić wartość A[2] z A[4] lub A[5]. Warto zauważyć, że prawy potomek ma mniejszą wartość od lewego potomka (8 jest mniejsze od 13). Żeby być pewnym, że nie popełnimy żadnego błędu sprawdzimy obie możliwości:

Okazuje się, że nie możemy zamienić węzła 2 z potomkiem o mniejszej wartości ( 5 ). Wiemy że wartość A[5] jest mniejsza od A[4], więc jeśli zamienimy węzły 2 i 5, to wrócimy do sytuacji początkowej – węzeł 2 wciąż nie będzie spełniał własności kopca.

Wniosek jest oczywisty – gdy musimy wybrać, z którym potomkiem należy się zamienić miejscami, zawsze wybieramy tego o większej wartości.

Uzgodniliśmy już, który węzeł zamieniamy, ale po dokonaniu tego zabiegu widać, że teraz węzeł 4 nie spełnia własności kopca. Powtórzmy jeszcze raz krok zamiany zgodnie z przyjętymi warunkami:

Doszliśmy do liścia, a jak wiadomo liście nie mają potomków więc kończymy algorytm. Otrzymaliśmy poprawie zbudowany kopiec. Przywracanie własności kopca zakończyło się sukcesem.

Teraz spróbujemy skonstuować ogólną definicję procedury KOPCUJ-MAX(A,i) (KOPCUJ-MIN(A,i) tworzy się analogicznie).

Wywołujemy procedurę KOPCUJ-MAX(A,i). Porównujemy ze sobą wartości: A[i], A[LEFT(i)] oraz A[RIGHT(i)] - któryś z nich jest największy. Jeżeli tym węzłem jest i to algorytm się zatrzymuje, bo dla tego węzła własność kopca jest zachowana. W przeciwnym wypadku zamieniamy i z potomkiem o największej wartości (jego indeks nazwiemy largest). Następnie musimy powtórzyć krok dla węzła largest, bo po zamianie ten węzeł ma wartość A[i] i dlatego poddrzewo doczepione do largest może nie spełniać własności kopca. Czyli wywołujemy KOPCUJ-MAX(A,largest).

Jeżeli nie wiesz czym jest logarytm, proponuję zajrzeć tutaj

Procedura KOPCUJ(A,i) wykonuje się w czasie O(log n), czyli w czasie logarytmicznym. Dla przykładu, gdyby kopiec miał 4 294 967 296 elementy, to procedura KOPCUJ(A,i) wykonała by najwyżej 32 kroki !! A to jest BARDZO MAŁO !

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com