Element minimalny, ze względu na porządek w zbiorze etykiet, znajduje się w korzeniu kopca. Znalezienie elementu minimalnego nie przedstawia więc żadnego problemu. Jeśli kopiec jest reprezentowany przez korzeń drzewa binarnego root typu node (por. wykład VI p4.), to aby poznać wartość elementu minimalnego kopca,  wystarczy sprawdzić wartość atrybutu  root.val.

Et min(root : node){ return root.val;}.

Uzasadnienie, że operacja min zwraca najmniejszą z etykiet przechowywanych w kopcu pozostawiamy Czytelnikowi.

Operacją, której poświęcimy więcej uwagi w tym punkcie, będzie operacja usuwania minimum, delmin,

delmin : Heap ® Heap,

polegająca na usunięciu z kopca elementu najmniejszego.   Ma ona następującą specyfikację: dla dowolnego H Î Heap i dowolnego e Î Et,

min(H) = e ® (min (delmin(H)) > e Ù  Ø member(e, delmin(H))).

Oczywiście, po wykonaniu tej operacji, powinniśmy otrzymać również kopiec. Usunięcie elementu minimalnego chcemy wykonać tak, by w jak najmniejszym stopniu modyfikować strukturę drzewa doskonałego. Nie możemy więc po prostu usunąć wierzchołka znajdującego się w korzeniu drzewa.

Metoda

Niech x będzie liściem znajdującym się najbardziej na prawo na ostatnim poziomie kopca H, tak jak zaznaczono na rysunku 9.4. Postępowanie składa się z trzech kroków:

1. Zastąp etykietę korzenia drzewa H, etykietą wierzchołka x.
2. Usuń wierzchołek x z drzewa H.
3. Jeżeli tak otrzymane drzewo nie jest kopcem, to zaczynając od korzenia, zamieniaj etykietę wierzchołka z etykietą tego z jego synów, którego etykieta jest mniejsza, tak długo, aż otrzymane drzewo będzie kopcem.

Przykład 3.1

Rozważmy drzewo z rysunku 9.2(a). Prześledźmy proces usuwania etykiety korzenia tego drzewa. Kolejne fazy algorytmu są zilustrowane na rysunkach 9.4(a), (b), (c). W pierwszym kroku zapamiętamy etykietę liścia (na rysunku 9.4(a) zaznaczony wierzchołek z etykietą 12) znajdującego się na ostatnim poziomie drzewa, najbardziej na prawo, i umieścimy ją w korzeniu drzewa (usuwając w ten sposób etykietę 1). Otrzymane drzewo jest doskonałe, nie jest jednak częściowo uporządkowane. Uporządkowanie poprawimy, zamieniając etykietę wierzchołka z mniejszym z jego synów, tak jak zaznaczono na rysunku 9.4(b), i kontynuując ten proces w górę drzewa tak długo, aż otrzymamy drzewo częściowo uporządkowane. Wynik przedstawiono na rysunku 9.4(c).

Koszt algorytmu delmin

Kroki 1 i 2 algorytmu mają stały koszt. W każdym kroku pętli 3, algorytm wykonuje co najwyżej dwa porównania (wybór najmniejszego z trzech elementów). Liczba iteracji jest równa długości przebytej ścieżki, a ta w najgorszym przypadku jest równa wysokości drzewa. Koszt całkowity wykonania operacji delmin możemy więc szacować z góry przez O(lg n).

Uwaga. Podobnie, jak w przypadku wstawiania, usuwanie minimum z drzewa-kopca sprawia trochę problemów. Chodzi o znalezienie ostatniego liścia, tego, którego etykieta wędruje na miejsce usuwanego minimum. Znów, jak w przypadku wstawiania, jedna referencja nie wystarczy, bo po usunięciu jednego elementu, trzeba będzie ją uaktualnić (umieć znów znaleźć ostatni liść). Zatem, byłoby najlepiej  mieć referencje  do "sąsiada" z lewej w każdym wierzchołku. Ponadto potrzebne są referencje do wierzchołka-ojca. Wszystko to wymaga dodatkowej pamięci rzędu liczby przechowywanych elementów. Inną, bardziej oszczędną,  implementację tego algorytmu poznamy w punkcie czwartym wykładu.

Pytanie 3:  Czy koszt algorytmu delmin, zastosowanego do kopca o 2^k wierzchołkach, można oszacować z góry przez 2*k ?

« poprzedni punkt

następny punkt »