4sol

7.5. KOLEJKI PRIORYTETOWE

rżenia pozostają kopcami, ale nowy korzeń może naruszać własność kopca (7.1). Jedyne, co trzeba zrobić, żeby przywrócić własność kopca, to raz wywołać HeapifyC/4, I), co pozostawi kopiec w A[l.. (n — 1)]. Algorytm heapsort powtarza ten proces dla kopca o rozmiarze n — 1, aż do uzyskania kopca

0    rozmiarze 2.

Heapsort(/4)

1    BUILD-HEAP(i4)

2    for i *- lengtłĄA] downto 2

3    do zamień A[l]++A[i]

4    heap-sizĄA) «- heap-sizĄA] — 1

5    HEAPJFY(zl, 1)

Na rysunku 7.4 widać przykład działania algorytmu heapsort po początkowym zbudowaniu kopca. Każdy kopiec jest pokazany na początku iteracji pętli for w wierszu 2.

Czas działania procedury Heapsort wynosi O(nlgn), ponieważ wywołanie BUILD-HJSAP zajmuje czas 0(n), a każde zn-1 wywołań llEAPiFY zajmuje czas 0(\gn).

Zadania

7.4- 1. Zilustruj (podobnie jak na rys. 7.4) działanie procedury Heapsort dla tablicy A = <5, 13, 2, 25, 7, 17, 20, 8, 4>.

7.4- 2. Jaki jest czas działania algorytmu heapsort dla tablicy A o długości n, która jest już posortowana rosnąco (malejąco)?

7.4- 3, Pokaż, że czas działania algorytmu heapsort wynosi lg n).

Wyszukiwarka

Podobne podstrony:
ALG9 5,5. Sterty i kolejki priorytetowe 139 liczbę 99 (patrz etap 5). Drzewo ma już 5-clcmentów, za
SAM63 (2) fefefca poKyka iią------w O IXXI wWm CMww KwmiM. May, ludzi*. wydv«mia lenie caratu, ale
C G Żagle mogą pozostać kartonowe, ale dobrze będzie dorysować im drugą stronę we własnym zakresie (
SAM63 (2) fefefca poKyka iią------w O IXXI wWm CMww KwmiM. May, ludzi*. wydv«mia lenie caratu, ale
Kolejki i priorytety Procesy oczekujące na zwolnienie procesora mogą mieć różną ważność.
WA30881 I902 SZSTEMATZCYNZ KURS 6 I djvu 253 typu, uległy rozkładowi, pozostała podnieta, ale pociąg
83701 zdj1 (6) Przywracanie własności kopca nakładamy, że drzewa binarne zaczepione w Left(/) i Rig
54083 SAM63 (2) fefefca poKyka iią------w O IXXI wWm CMww KwmiM. May, ludzi*. wydv«mia lenie caratu
ALG1 5.5. Sterty i kolejki priorytetowe 141 Treść procedury DoGory nie powinna stanowić niespodzian
ALG3 5.5. Sterty i kolejki priorytetowe 143 Wystarczy bowiem dowolną tablicę do posortowania wpierw
przedświadome - fakty, zdarzenia, spostrzeżenia, które pozostają w nieświadomość, ale mogę być łatwo
DSCN9607 SIE UlYWALEM LEKÓW I LEKARZY. Sie używałem leków i lekarzy. O! moi bracia, chcąc pozostać i
ALG7 137 5.5. Sterty i kolejki priorytetowe Jednym z najłatwiejszych sposobów realizacji kolejek pr
Slajd47 (70) Priorytety przerwań Oczywistym faktem jest, że nie może realizować się kilka
page0443 44I TEOLOOJA PRAW. Ale dusza nie może być bez przymiotów swoich; jeżeli ona sama dawniejsza
skanuj0101 tylko język ogólny, ale również, co może brzmieć paradoksalnie, pewne specyficzne właściw
11291 IMGp55 (3) M.    E tam, ale to dobrze. N.    Może więc mogłybyśm

więcej podobnych podstron