Jednym z najczęstszych zastosowań kopca jest użycie go do rozwiązania problemu sortowania. 

Niech będzie dana tablica TAB złożona z n różnych elementów i  niech zadanie polega na takim uporządkowaniu  elementów tej tablicy, by TAB[i] > TAB[i+1] dla wszystkich 0< i < n.

Metoda

1. Zbuduj kopiec, którego etykietami wierzchołków są elementy danej tablicy.
2. Odczytaj i usuń z kopca kolejne elementy minimalne.

Algorytm oparty na tej metodzie nosi nazwę algorytmu HeapSort. Do skonstruowania kopca w tablicy TAB użyjemy algorytmu construct, a do poprawiania struktury - algorytmu  DownHeap. Wynik działania algorytmu  HeapSort zapiszemy ponownie w tablicy TAB.

Algorytm HeapSort

Poprawność  algorytmu

Niech n oznacza liczbę elementów w tablicy TAB. Niezmiennikiem pętli w tym algorytmie jest formuła:

Elementy  TAB[1],...,TAB[k] tworzą kopiec, k ³ 0  oraz

dla i = k+1, ..., n-1, TAB[i] > TAB[i+1]           (*)

mówiąca, że elementy tablicy na pozycjach k+1, ..., n tworzą ciąg uporządkowany malejąco. 

Rzeczywiście, jeżeli własność (*) jest spełniona na początku pewnej iteracji pętli "while", to po wykonaniu instrukcji "swap(TAB[1], TAB[k])", minimum w aktualnie rozważanym kopcu zostanie umieszczone na pozycji k-tej. Jest to element większy od wszystkich wcześniej usuniętych z kopca elementów, oraz najmniejszy w aktualnie istniejącym kopcu.  Zatem ciąg TAB[k], TAB[k+1],..., jest uporządkowany malejąco. Po wykonaniu instrukcji "k := k-1" wracamy do własności (*).  Chociaż instrukcja "swap(TAB[1], TAB[k])" zaburzyła własność częściowego uporządkowania na pozycjach aktualnie zajmowanych przez kopiec, to algorytm "DownHeap(TAB, k,1);" poprawi odpowiednio ścieżkę, tak że po jego wykonaniu  pozycje od 1 do k tablicy TAB znów reprezentują kopiec.

Przed wykonaniem pętli  elementy na pozycjach od 1 do k tworzą kopiec i trywialnie spełniona jest własność (*). Wynika stąd, że po wykonaniu pętli, niezmiennik znów będzie spełniony oraz k=0.  Oznacza to, że wszystkie elementy tablicy TAB tworzą  po wykonaniu pętli ciąg malejący.

Koszt algorytmu

Oczywiście operacją dominującą jest w tym algorytmie porównywanie elementów. Pierwsza część algorytmu- konstrukcja kopca w tablicy wymaga, jak wiemy O(n) porównań. Ponieważ pętla "while" jest wykonywana dla każdego usuwanego elementu, tzn. n razy, a w każdej iteracji musimy poprawić uporządkowanie na jednej ścieżce o długości co najwyżej ëlg (k+1)û, gdzie k jest liczbą elementów aktualnie rozważanego kopca. Zatem koszt algorytmu można oszacować przez O(n ´ lg n). Wynika stąd, że algorytm HeapSort należy do najszybszych algorytmów, sortujących przez porównywanie elementów.

Zwróćmy jeszcze uwagę na to, że algorytm Heapsort nie musi wykorzystywać żadnej dodatkowej pamięci: sortuje w miejscu. 

Przykład 6.1

Rozważmy tablicę (a) przedstawioną na rysunku 9.8. Pierwszy etap algorytmu polega na zastosowaniu algorytmu construct konstrukcji kopca w tablicy. Pierwszą pozycją odpowiadającą wierzchołkowi wewnętrznemu jest pozycja 6. Ponieważ uporządkowanie na ścieżce nie jest poprawne (11> 1), zamieniamy miejscami te dwa elementy. W wyniku otrzymamy tablicę (b). Ścieżki drzewa zaczynające się od pozycji 5 i 4 są poprawnie uporządkowane, natomiast trzeba poprawić ścieżkę zaczynającą się od pozycji 3.Wynikiem jest tablica (c). Ścieżki zaczynające się  od pozycji 2 są poprawnie uporządkowane. Pozostaje poprawić ścieżki zaczynające się od pozycji 1. Wynik działania algorytmu construct przedstawia tablica (d).  Teraz zaczynamy sukcesywne usuwanie elementu minimalnego. Usuwany element zapisujemy na zwalnianych pozycjach od końcu tabeli. Zaznaczone na czerwono kratki wskazują elementy, które pojawiły się w wyniku usunięcia elementu minimalnego i spowodowały utratę własności częściowego porządku. Na przykład 11 pojawiło się w korzeniu zamiast usuniętej jedynki (tabela e). Musimy więc poprawić ścieżki, tak jak to robiliśmy w algorytmie delmin. Wynikiem jest tabela (f). Wynik czterech iteracji pętli w algorytmie HeapSort zapisano w tabeli (l). Zachęcam Czytelnika do samodzielnego dokończenia wykonania algorytmu.J

Uwaga. Algorytm HeapSort może być również zastosowany do sortowania danego ciągu w porządku rosnącym. Wystarczy zastosować w tym celu uporządkować kopiec ze względu na relację ³.

Pytanie 7: Ile porównań wykona algorytm HeapSort do posortowania tablicy zawierającej elementy 1,2,3,4,5?
 

« poprzedni punkt

następny punkt »