Tworzenie tablicy reprezentującej kopiec o n elementach przy użyciu operacji insert, tzn. przez kolejne wstawiane elementów, jest dość kosztowne. Jeśli liczba elementów wynosi n, to koszt utworzenia  kopca w tablicy wynosi O(n ´ lg n). Jeżeli  liczba elementów w kopcu nie jest z góry znana, to musi to się odbyć właśnie w taki sposób. Jeśli natomiast, znamy z góry liczbę elementów w kopcu, to koszt utworzenia kopca można zmniejszyć do liniowego. Algorytm konstrukcji kopca w tablicy został przedstawiony jako procedura Construct. Procedura ta wykorzystuje proces poprawiania ścieżki, o którym była mowa w poprzednim punkcie.

Dana jest tablica TAB o n elementach. Zadanie polega na takim przeorganizowaniu elementów tej tablicy, by reprezentowała ona kopiec, tzn. chcemy by spełniona była własność częściowego uporządkowania:

("i) (2i £ n ®TAB[i] < TAB[2i]) Ù (2i+1 £ n ® TAB[i] < TAB[2i+1]).     (*)

Idea algorytmu polega na dwóch obserwacjach:

1. Połowa elementów w tablicy odpowiada liściom drzewa, a więc warunek (*) jest dla tych elementów trywialnie spełniony.

2. Jeżeli zostały utworzone kopce A i B o korzeniach na pozycjach 2i oraz 2i+1, to albo etykieta na pozycji i-tej jest mniejsza od TAB[2i], TAB[2i+1] i wtedy mamy kopiec o korzeniu na pozycji i-tej, albo tak nie jest, i wtedy trzeba poprawić jedną  ścieżkę "w dół drzewa", tak jak w algorytmie usuwania elementu minimalnego.

Algorytm konstrukcji kopca w tablicy.

Zgodnie z opisaną ideą, algorytm konstrukcji kopca w tablicy, polega na sukcesywnym poprawianiu, jeśli trzeba, częściowego uporządkowania kopców, których korzenie znajdują się kolejno na pozycjach n div 2, n div 2-1, ..., 1.

Analiza poprawności algorytmu

Niezmiennikiem pętli "while" jest tu formuła mówiąca, że na wszystkich pozycjach tablicy TAB począwszy od k+1 do n  znajdują się korzenie poprawnie zbudowanych kopców. Są to kopce jednoelementowe. Jeśli procedura DownHeap utworzy kopiec o korzeniu TAB[k],  i wykonamy instrukcję "k := k-1;", to po wykonaniu treści pętli znów spełniony jest niezmiennik. Po wykonaniu całej pętli, na pozycji 1 w tablicy TAB znajduje się korzeń kopca, którego etykietami są elementy tablicy TAB.

Koszt algorytmu

Niech n będzie liczbą elementów w kopcu, a h jego wysokością, h= ëlg(n+1)û. Oszacujemy koszt algorytmu budowy kopca w tablicy w przypadku pesymistycznym.  Przypomnijmy, że liczba porównań wykonanych przez algorytm DownHeap(TAB, x) zależy od długości drogi od wierzchołka  x od liścia i wymaga w każdym kroku co najwyżej dwóch porównań dla ustalenia właściwej zależności między etykietą wierzchołka i jego następnikami. Dla ścieżki o długości i wykonamy co najwyżej 2i porównań. Mamy:

W(n) £ S _i=1,...,h  2^h-i ´ 2i .

Sumowanie rozciąga się od 1 do h ponieważ rozważamy tylko wierzchołki wewnętrzne drzewa, a  2^h-i odpowiada maksymalnej liczbie wierzchołków odległych o i krawędzi od liści drzewa. Po przekształceniu otrzymujemy:

W(n) = 2^h+1 S_i=1,...,h  2^-i ´ i = 2^h+1 (1 ´ 2^-1 + 2 ´ 2^-2 + 3 ´ 2^-3 +...+ h ´ 2^-h) =

2^h+1 (S_j=1,...,h  (S_i=j,...,h2^-i) = 2^h+1 (S_j=1,...,h  (S_s=0,...,h 2^-(j+s)) £

2^h+1 (S_j=1,...,h 2^-j (S_s=0,...,+¥ 2^-s) £ 2^h+1 (S_j=1,...,h 2^-j (1/(1-1/2)) =

 2^h+2 (S_j=1,...,h 2^-j ) =  2^h+2 (1- 1/2^h+1)/(1/2) =  2^h+3 -4 = 4´2^h+1 - 4 = 4n = Q(n).

Analogicznie najlepszy możliwy koszt tego algorytmu możemy oszacować przez 

S_i=1,...,h 2^h-i ´ 2 = 2^h+1 S_i=1,...,h 2^-i  = 2n -1 = Q(n).

Wynika stąd, że koszt algorytmu konstrukcji kopca w tablicy jest liniowy.

Pytanie 6: Niech A będzie kopcem o 200 wierzchołkach, a B kopcem o 127 wierzchołkach. Niech etykietami obu drzew będą liczby naturalne większe od zera. Czy drzewo postaci <A, 0, B>, powstałe z połączenia drzew A i B, jest kopcem?

« poprzedni punkt

następny punkt »