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).