1800320377

Rysunek ukazujący działanie algorytmu na prostym kopcu 5 elementowym:

II

F.

F

C.

FT“1

2 4 U li

© H»M"1 ^—*

Rys. 2 Sortowanie przez kopcowanie na kopcu 5-elementovvym typu max proszę zauważyć że w kroku A przywraca się porządek kopca

3. Usprawnienia i modyfikacje algorytmu

Trudno jest usprawnić algorytm, który i tak jest już bardzo sprawny, jednak wyróżniamy 2 podstawowe modyfikacje:

a) Koncepcja Floyda

Koncepcja Floyda, polega na zauważeniu, iż element ponownie wstawiony do kopca podczas procesu wysortowywania, przebywa z reguły całą drogę w dół. Możemy więc zaoszczędzić czas unikając sprawdzenia, czy element trafił na pozycję, promując większego z synów do czasu osiągnięcia najniższego

poziomu, a potem przesuwając z powrotem w górę kopca na właściwe miejsce. Ten pomysł pozwala zmniejszyć liczbę porównań asymptotycznie dwukrotnie - blisko wartości:

będącym absolutnym minimum dla liczby porównań algorytmu sortowania. Metoda ta wymaga stosowania dodatkowej ewidencji i jest przydatna w praktyce tylko wtedy gdy koszt porównań jest stosunkowo wysoki(np. gdy sortuje się rekordy z łańcuchami znaków albo z innymi typami długich kluczy).

b) Kopiec oparty na tablicowej reprezentacji pełnego drzewa trynarnego (trójkowego)

Inna koncepcja usprawnienia polega na zbudowaniu kopca opartego na tablicowej reprezentacji pewnego drzewa trynarnego (trójkowego),