Heapsort - Heapsort

Heapsort

Spousta hromadného třídění pole náhodně permutovaných hodnot. V první fázi algoritmu jsou prvky pole přeuspořádány, aby uspokojily vlastnost haldy . Před samotným tříděním se pro ilustraci krátce zobrazí stromová struktura haldy.
Třída	Algoritmus řazení
Datová struktura	Pole
Nejhorší výkon	${\ Displaystyle O (n \ log n)}$
Nejlepší výkon	${\ Displaystyle O (n \ log n)}$(různé klíče) nebo (stejné klíče)${\ Displaystyle O (n)}$
Průměrný výkon	${\ Displaystyle O (n \ log n)}$
Nejhorší prostorová složitost	${\ Displaystyle O (n)}$totální pomocný${\ displaystyle O (1)}$

V počítačové vědě je heapsort srovnávacím algoritmem založeným na srovnání . Heapsort lze považovat za vylepšené výběrové řazení : podobně jako výběrové řazení, heapsort rozděluje svůj vstup do seřazené a netříděné oblasti a iterativně zmenšuje netříděnou oblast tak, že z ní extrahuje největší prvek a vloží ji do seřazené oblasti. Na rozdíl od výběrového třídění heapsort neztrácí čas lineárním skenováním netříděné oblasti; spíše halda třídění udržuje netříděnou oblast ve struktuře haldy dat, aby rychleji našla největší prvek v každém kroku.

Ačkoli je v praxi na většině strojů poněkud pomalejší než dobře implementovaný quicksort , má výhodu příznivějšího běhu O ( n log n ) v nejhorším případě . Heapsort je zavedený algoritmus , ale není stabilní .

Heapsort vynalezl JWJ Williams v roce 1964. To byl také zrod hromady, kterou již Williams představil jako užitečnou datovou strukturu. Ve stejném roce vydal RW Floyd vylepšenou verzi, která by mohla řadit pole na místě, a pokračovat tak ve svém dřívějším výzkumu algoritmu stromové řady .

Přehled

Algoritmus heapsortu lze rozdělit na dvě části.

V prvním kroku je halda je postaven z dat (viz binární halda § Budování haldy ). Halda je často umístěna v poli s rozložením kompletního binárního stromu . Kompletní binární strom mapuje binární stromovou strukturu do indexů pole; každý index pole představuje uzel; index rodiče uzlu, levé podřízené větve nebo pravé podřízené větve jsou jednoduché výrazy. U pole založeného na nule je kořenový uzel uložen na indexu 0; pokud ije index aktuálního uzlu, pak

  iParent(i)     = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer.
  iLeftChild(i)  = 2*i + 1
  iRightChild(i) = 2*i + 2

V druhém kroku je seřazené pole vytvořeno opakovaným odebráním největšího prvku z haldy (kořen haldy) a jeho vložením do pole. Halda se aktualizuje po každém odebrání, aby byla zachována vlastnost haldy. Jakmile jsou všechny objekty odstraněny z haldy, výsledkem je seřazené pole.

Heapsort lze provádět na místě. Pole lze rozdělit na dvě části, seřazené pole a haldu. Skladování hromad jako pole je diagrammed zde . Hromada invariantu je zachována po každé extrakci, takže jedinou cenou jsou náklady na extrakci.

Algoritmus

Algoritmus Heapsort zahrnuje přípravu seznamu tak, že jej nejprve změníte na maximální hromadu . Algoritmus pak opakovaně prohodí první hodnotu seznamu s poslední hodnotou, sníží rozsah hodnot uvažovaných v haldě o jednu a proseje novou první hodnotu do své polohy v haldě. To se opakuje, dokud není rozsah uvažovaných hodnot o jednu hodnotu na délku.

Kroky jsou následující:

1. Zavolejte funkci buildMaxHeap () v seznamu. Také označovaný jako heapify (), vytváří hromadu ze seznamu v operacích O (n).
2. Vyměňte první prvek seznamu za poslední prvek. Snižte uvažovaný rozsah seznamu o jeden.
3. Voláním funkce siftDown () v seznamu přesuňte nový první prvek na příslušný index v haldě.
4. Přejděte ke kroku (2), pokud uvažovaný rozsah seznamu není jeden prvek.

Operace buildMaxHeap () je spuštěna jednou a má O ( n ) výkon. Funkce siftDown () je O (log n ) a je volána nkrát . Výkon tohoto algoritmu je tedy O ( n + n log n ) = O ( n log n ) .

Pseudo kód

Následuje jednoduchý způsob implementace algoritmu v pseudokódu . Pole jsou nulová a swapslouží k výměně dvou prvků pole. Pohyb „dolů“ znamená od kořene směrem k listům nebo od nižších indexů k vyšším. Všimněte si toho, že během řazení je největší prvek u kořene haldy v a[0], zatímco na konci řazení je největší prvek in a[end].

procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (the heap size is reduced by one)
        end ← end - 1
        (the swap ruined the heap property, so restore it)
        siftDown(a, 0, end)

Rutina třídění používá dva podprogramy heapifya siftDown. První z nich je běžnou rutinou stavby haldy na místě, zatímco druhá je běžným podprogramem pro implementaci heapify.

(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
    (start is assigned the index in 'a' of the last parent node)
    (the last element in a 0-based array is at index count-1; find the parent of that element)
    start ← iParent(count-1)
    
    while start ≥ 0 do
        (sift down the node at index 'start' to the proper place such that all nodes below
         the start index are in heap order)
        siftDown(a, start, count - 1)
        (go to the next parent node)
        start ← start - 1
    (after sifting down the root all nodes/elements are in heap order)

(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, start, end) is
    root ← start

    while iLeftChild(root) ≤ end do    (While the root has at least one child)
        child ← iLeftChild(root)   (Left child of root)
        swap ← root                (Keeps track of child to swap with)

        if a[swap] < a[child] then
            swap ← child
        (If there is a right child and that child is greater)
        if child+1 ≤ end and a[swap] < a[child+1] then
            swap ← child + 1
        if swap = root then
            (The root holds the largest element. Since we assume the heaps rooted at the
             children are valid, this means that we are done.)
            return
        else
            swap(a[root], a[swap])
            root ← swap            (repeat to continue sifting down the child now)

heapifyPostup si lze představit jako stavba hromadu zdola nahoru postupným prosévání směrem dolů pro stanovení vlastnosti haldy . Jednodušší na pochopení může být alternativní verze (zobrazená níže), která vytváří hromadu shora dolů a posouvá nahoru. Tuto siftUpverzi lze zobrazit jako počínaje prázdnou hromadou a postupným vkládáním prvků, zatímco siftDownvýše uvedená verze považuje celé vstupní pole za plnou, ale „rozbitou“ hromadu a „opravuje“ ji od poslední netriviální dílčí hromady ( tj. poslední nadřazený uzel).

Rozdíl v časové složitosti mezi verzí „siftDown“ a verzí „siftUp“.

Také siftDownverze heapify má O ( n ) složitost , zatímco siftUpverze uvedené dále obsahuje O ( n log n ) složitost vzhledem k jeho rovnocennosti vložení každý prvek, jeden po druhém, do prázdné haldy. To se může zdát neintuitivní, protože na první pohled je zřejmé, že první z nich volá na svou logaritmickou časovou prosévací funkci jen polovinu hovorů; tj. zdá se, že se liší pouze konstantním faktorem, který nikdy neovlivňuje asymptotickou analýzu.

Abyste pochopili intuici za tímto rozdílem ve složitosti, všimněte si, že počet swapů, které mohou nastat během jakéhokoli jednoho siftUp hovoru, roste s hloubkou uzlu, na kterém je volání uskutečněno. Podstatou je, že existuje mnoho (exponenciálně mnoho) více "hlubokých" uzlů, než je počet "mělkých" uzlů v hromadě, takže siftUp může mít svůj plný logaritmický čas běhu na přibližně lineárním počtu hovorů provedených na uzlech na nebo blízko „dna“ haldy. Na druhé straně se počet swapů, ke kterým může dojít během kteréhokoli volání siftDown, snižuje se zvyšující se hloubkou uzlu, na kterém je volání uskutečněno. Když tedy siftDown heapifyzačíná a volá siftDownna spodní a nejpočetnější vrstvy uzlů, každé prosévací volání způsobí nanejvýš počet swapů rovných „výšce“ (ze spodní části hromady) uzlu, na kterém proběhne prosévání. Jinými slovy, asi polovina hovorů na siftDown bude mít maximálně jen jeden swap, pak asi čtvrtina hovorů bude mít maximálně dva swapy atd.

Algoritmus heapsortu má časovou složitost O ( n log n ) s použitím jedné z verzí heapify.

 procedure heapify(a,count) is
     (end is assigned the index of the first (left) child of the root)
     end := 1
     
     while end < count
         (sift up the node at index end to the proper place such that all nodes above
          the end index are in heap order)
         siftUp(a, 0, end)
         end := end + 1
     (after sifting up the last node all nodes are in heap order)
 
 procedure siftUp(a, start, end) is
     input:  start represents the limit of how far up the heap to sift.
                   end is the node to sift up.
     child := end 
     while child > start
         parent := iParent(child)
         if a[parent] < a[child] then (out of max-heap order)
             swap(a[parent], a[child])
             child := parent (repeat to continue sifting up the parent now)
         else
             return

Všimněte si toho, že na rozdíl od siftDownpřístupu, kde po každém swapu potřebujete volat pouze siftDownpodprogram, abyste opravili rozbitou hromadu; siftUpsám podprogram nelze opravit rozbité haldy. Hromadu je třeba sestavit pokaždé po výměně voláním heapifyprocedury, protože „siftUp“ předpokládá, že vyměněný prvek skončí na svém konečném místě, na rozdíl od „siftDown“ umožňuje průběžné úpravy položek níže v haldě, dokud invariant je spokojený. Upravený pseudokód pro použití siftUppřístupu je uveden níže.

 procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (rebuild the heap using siftUp after the swap ruins the heap property)
        heapify(a, end)
        (reduce the heap size by one)
        end ← end - 1

Variace

Floydova hromádková konstrukce

Nejdůležitější změna na základní algoritmus, která je obsažena ve všech praktických implementací je haldy konstrukce algoritmus Floyd, který běží v O ( n ) času a použití siftdown spíše než siftup , čímž odpadá nutnost provádět siftup vůbec.

Floydův algoritmus nezačíná triviální hromadou a opakovaně přidává listy, ale začíná listy a pozoruje, že jsou triviální, ale samy o sobě platné hromady, a poté přidá rodiče. Počínaje prvkem n /2 a pracujícím pozpátku se každý vnitřní uzel stane kořenem platné hromady proosetím dolů. Posledním krokem je prosazení prvního prvku, po kterém se celé pole řídí vlastností haldy.

Je známo, že nejhorší případ srovnání během Floydovy hromady konstrukce Heapsortu je roven 2 n -2 s ₂ ( n ) -e ₂ ( n ) , kde s ₂ ( n ) je počet 1 bitů v binární reprezentaci n a e ₂ ( n ) je počet koncových 0 bitů.

Standardní implementace Floydova algoritmu konstrukce haldy způsobuje velký počet chyb mezipaměti, jakmile velikost dat překročí velikost mezipaměti CPU . Mnohem lepšího výkonu na velkých datových sadách lze dosáhnout sloučením v hloubce prvního řádu, kombinací subheapů co nejdříve, než kombinováním všech subheapů na jedné úrovni, než přejdete k té výše.

Hortort zdola nahoru

Hortort shora dolů je varianta, která snižuje počet srovnání požadovaných významným faktorem. Zatímco běžný heapsort vyžaduje srovnání 2 n log ₂ n + O ( n ) v nejhorším případě a v průměru, varianta zdola nahoru vyžaduje v průměru n log ₂ n + O (1) srovnání a 1,5 n log ₂ n + O ( n ) v nejhorším případě.

Pokud jsou srovnání levná (např. Celočíselné klíče), pak je rozdíl nedůležitý, protože halda shora dolů porovnává hodnoty, které již byly načteny z paměti. Pokud však srovnání vyžaduje volání funkce nebo jinou složitou logiku, pak je výhodné shora dolů.

Toho je dosaženo zlepšením siftDownpostupu. Tato změna poněkud zlepšuje fázi vytváření haldy v lineárním čase, ale je významnější ve druhé fázi. Jako obyčejné heapsort každé iterace druhé fáze extrahuje vrcholu haldy, [0] , a vyplňuje mezeru opouští se s [ konec ] , potom tento druhý prvek sifts dolů haldy. Ale tento prvek pochází z nejnižší úrovně hromady, což znamená, že je jedním z nejmenších prvků v hromadě, takže prosévání pravděpodobně provede mnoho kroků, aby se přesunulo zpět dolů. V běžném heapsortu každý krok procházení dolů vyžaduje dvě srovnání, aby se našly minimálně tři prvky: nový uzel a jeho dvě podřízené položky.

Hortort zdola nahoru místo toho najde cestu největších dětí k úrovni listu stromu (jako by vkládal −∞) pomocí pouze jednoho srovnání na úroveň. Jinak řečeno, najde list, který má tu vlastnost, že on a všichni jeho předkové jsou větší nebo rovni svým sourozencům. (V nepřítomnosti stejných klíčů, tento list je unikátní.) Potom, z tohoto listu, hledá vzhůru (za použití jedno srovnání za level) pro správné polohy v této cestě vložit na [ konec ] . Toto je stejné umístění jako u běžných heapsortů a vyžaduje stejný počet výměn k provedení vložení, ale k nalezení tohoto umístění je zapotřebí méně srovnání.

Protože jde až úplně dolů a pak se vrací nahoru, u některých autorů se tomu říká heapsort with bounce .

function leafSearch(a, i, end) is
    j ← i
    while iRightChild(j) ≤ end do
        (Determine which of j's two children is the greater)
        if a[iRightChild(j)] > a[iLeftChild(j)] then
            j ← iRightChild(j)
        else
            j ← iLeftChild(j)
    (At the last level, there might be only one child)
    if iLeftChild(j) ≤ end then
        j ← iLeftChild(j)
    return j

Návratová hodnota parametru leafSearchse používá v upravené siftDownrutině:

procedure siftDown(a, i, end) is
    j ← leafSearch(a, i, end)
    while a[i] > a[j] do
        j ← iParent(j)
    x ← a[j]
    a[j] ← a[i]
    while j > i do
        swap x, a[iParent(j)]
        j ← iParent(j)

Hpsort shora dolů byl oznámen jako bití quicksortu (s výběrem pivotů ze tří mediánů) na polích o velikosti ≥16000.

Přehodnocení tohoto algoritmu v roce 2008 ukázalo, že není rychlejší než běžný heapsort pro celočíselné klíče, pravděpodobně proto, že moderní predikce větví ruší náklady na předvídatelná srovnání, kterým se heapsortu zdola nahoru daří vyhýbat.

Další upřesnění provede binární vyhledávání v cestě k vybranému listu a v nejhorším případě seřadí ( n +1) (log ₂ ( n +1) + log ₂ log ₂ ( n +1) + 1,82) + O (log ₂ n ) srovnání, blíží informace-teoretická dolní odhad z n log ₂ n - 1.4427 n srovnání.

Varianta, která používá dva extra bity na interní uzel (celkem n -1 bitů pro hromadu n -prvků) k ukládání informací o tom, které dítě je větší (dva bity jsou nutné k uložení tří případů: vlevo, vpravo a neznámo) používá méně než n log ₂ n + 1,1 n porovnává.

Jiné variace

• Ternární heapsort používá místo binární hromady ternární hromadu; to znamená, že každý prvek v hromadě má tři děti. Programování je složitější, ale provádí konstantní počet opakování operací swapu a porovnávání. Důvodem je, že každý krok třídění dolů v ternární hromadě vyžaduje tři srovnání a jeden swap, zatímco v binární hromadě jsou požadována dvě srovnání a jeden swap. Dvě úrovně v ternární hromadě pokrývají 3 ² = 9 prvků, více práce se stejným počtem srovnání jako tři úrovně v binární hromadě, které pokrývají pouze 2 ³ = 8. To je primárně akademického zájmu, nebo jako studentské cvičení , protože dodatečná složitost nestojí za menší úspory a heapsort zdola nahoru poráží obojí.
• Paměťově optimalizovaný heapsort vylepšuje referenční lokalitu heapsortu tím, že ještě více zvyšuje počet dětí. To zvyšuje počet srovnání, ale protože jsou všechny podřízené uloženy postupně v paměti, snižuje se počet linek mezipaměti přístupných během procházení haldy, což je zlepšení čistého výkonu.
• Mimořádný heapsort se zlepšuje u heapsortu zdola nahoru tím, že odstraní nejhorší případ a zaručí n log ₂ n + O ( n ) srovnání. Když se vezme maximum, místo vyplnění uvolněného místa netříděnou datovou hodnotou jej vyplňte hodnotou −∞ sentinelu, která nikdy „neodskakuje“ zpět. Ukazuje se, že to lze použít jako primitiv v místním (a nerekurzivním) algoritmu „QuickHeapsort“. Nejprve provedete průchod oddílů podobný quicksortu, ale obrátíte pořadí rozdělených dat v poli. Předpokládejme ( bez ztráty obecnosti ), že menší oddíl je ten větší než pivot, který by měl jít na konec pole, ale náš obrácený krok dělení jej umístí na začátek. Vytvořte hromadu z menšího oddílu a proveďte na něm hromadné hromadění a vyměňte extrahovaná maxima s hodnotami z konce pole. Ty jsou menší než pivot, což znamená méně než jakákoli hodnota v haldě, takže slouží jako −∞ hodnoty sentinuly . Jakmile je heapsort dokončen (a pivot přesunut těsně před nyní seřazený konec pole), pořadí oddílů bylo obráceno a větší oddíl na začátku pole může být seřazen stejným způsobem. (Protože neexistuje žádná rekurze bez ocasu , toto také eliminuje využití zásobníku O (log n ) quicksortu .)
• Smoothsort algoritmus je variace heapsort vyvinutý Edsger Dijkstra v roce 1981. Stejně jako heapsort, smoothsort je horní hranice je O ( n log n ) . Výhodou smoothsortu je, že se blíží času O ( n ), pokud je vstup již do určité míry seřazen , zatímco heapsort průměruje O ( n log n ) bez ohledu na počáteční seřazený stav. Kvůli své složitosti se smoothsort používá jen zřídka.
• Levcopoulos a Petersson popisují variantu hromádky založenou na hromadě karteziánských stromů . Nejprve je ze vstupu vytvořen kartézský strom v čase O ( n ) a jeho kořen je umístěn do 1prvkové binární hromady. Potom opakovaně extrahujeme minimum z binární hromady, vygenerujeme kořenový prvek stromu a přidáme jeho levé a pravé potomstvo (pokud existuje), což jsou samy karteziánské stromy, do binární hromady. Jak ukazují, pokud je vstup již téměř setříděn, karteziánské stromy budou velmi nevyvážené, s několika uzly s levými a pravými dětmi, což způsobí, že binární hromada zůstane malá, a umožní algoritmu třídit rychleji než O ( n log n ) pro vstupy, které jsou již téměř tříděny.
• Několik variant, jako je slabý heapsort, vyžaduje v nejhorším případě n log ₂ n + O (1) srovnání, blízké teoretickému minimu, s použitím jednoho dalšího bitu stavu na uzel. I když tento extra bit dělá algoritmy opravdu ne na místě, pokud pro ně lze najít prostor uvnitř prvku, tyto algoritmy jsou jednoduché a efektivní, ale stále pomalejší než binární hromady, pokud jsou srovnání klíčů dostatečně levné (např. Celočíselné klíče), že na konstantním faktoru nezáleží.
• Katajainenův „konečný heapsort“ nevyžaduje žádné další úložiště, provádí srovnání n log ₂ n + O (1) a podobný počet tahů prvků. Je však ještě složitější a není odůvodněné, pokud není srovnání velmi drahé.

Srovnání s jinými druhy

Heapsort primárně soutěží s quicksortem , dalším velmi efektivním obecným algoritmem řazení založeným na porovnávání na místě.

Hlavními výhodami Heapsortu je jeho jednoduchý, nerekurzivní kód, minimální požadavek na pomocné úložiště a spolehlivě dobrý výkon: jeho nejlepší a nejhorší případy jsou navzájem v malém konstantním faktoru a v teoretické dolní hranici srovnávacích druhů . I když to nemůže být lepší než O ( n log n ) pro předem seřazené vstupy, netrpí ani nejhorším případem O ( n ² ) quicksortu . ( Tomu poslednímu se lze vyhnout pečlivou implementací, ale díky tomu je quicksort mnohem složitější a jedno z nejpopulárnějších řešení, introsort , používá pro tento účel heapsort.)

Jeho hlavní nevýhodou je špatná referenční lokalita a inherentně sériový charakter; přístupy k implicitnímu stromu jsou široce rozptýlené a většinou náhodné a neexistuje žádný přímý způsob, jak jej převést na paralelní algoritmus .

Díky tomu je populární ve vestavěných systémech , v reálném čase a v systémech zabývajících se zlomyslně zvolenými vstupy, jako je například jádro Linuxu. Je to také dobrá volba pro každou aplikaci, která neočekává se bottlenecked na třídění.

Dobře implementovaný quicksort je obvykle 2–3krát rychlejší než heapsort. Přestože quicksort vyžaduje méně srovnání, je to jen malý faktor. (Výsledky tvrdí, že dvakrát tolik srovnání měří verzi shora dolů; viz § Hromadný shora dolů .) Hlavní výhodou rychlého řazení je jeho mnohem lepší referenční lokalita: dělení je lineární skenování s dobrou prostorovou lokalitou a rekurzivní dělení má dobrou časovou lokalitu. S dalším úsilím lze quicksort implementovat také do kódu většinou bez větví a k paralelnímu třídění dílčích oddílů lze použít více procesorů. Rychlé řazení je tedy upřednostňováno, pokud dodatečný výkon odůvodňuje úsilí o implementaci.

Druhým hlavním algoritmem řazení O ( n log n ) je sloučení , které ale jen zřídka přímo konkuruje heapsortu, protože není na místě. Požadavek na sloučení řazení pro Ω ( n ) extra prostor (zhruba poloviční velikost vstupu) je obvykle prohibitivní, kromě situací, kdy má sloučení řazení jasnou výhodu:

• Když je vyžadováno stabilní třídění
• Při využití výhod (částečně) předem tříděného vstupu
• Třídění propojených seznamů (v takovém případě slučovací řazení vyžaduje minimální prostor navíc)
• Paralelní třídění; merge sort paralelizuje ještě lépe než quicksort a lze snadno dosáhnout téměř lineárního zrychlení
• Externí třídění ; merge sort má vynikající referenční lokalitu

Příklad

Nechť {6, 5, 3, 1, 8, 7, 2, 4} je seznam, který chceme seřadit od nejmenšího po největší. ) .)

Příklad na heapsortu.

Poznámky

Reference

• Williams, JWJ (1964), „Algoritmus 232 - Heapsort“, komunikace ACM , 7 (6): 347–348, doi : 10,1145/512274.512284
• Floyd, Robert W. (1964), „Algorithm 245 - Treesort 3“, Communications of the ACM , 7 (12): 701, doi : 10.1145/355588.365103 , S2CID  52864987
• Carlsson, Svante (1987), „Výsledky průměrných případů na heapsortu“, BIT , 27 (1): 2–17, doi : 10,1007/bf01937350 , S2CID  31450060
• Knuth, Donald (1997), „§5.2.3, Třídění podle výběru“, Třídění a vyhledávání , Umění počítačového programování , 3 (třetí ed.), Addison-Wesley, s. 144–155, ISBN 978-0-201-89685-5
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein . Úvod do algoritmů , druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN  0-262-03293-7 . Kapitoly 6 a 7 respektive: Heapsort a prioritní fronty
• PDF původního papíru Dijkstra na Smoothsort
• Heaps and Heapsort Tutorial David Carlson, St. Vincent College

externí odkazy

• Algoritmy animovaného třídění: Heap Sort at Wayback Machine (archivováno 6. března 2015) - grafická ukázka
• Courseware on Heapsort od Univ. Oldenburg - S textem, animacemi a interaktivními cvičeními
• NIST's Dictionary of Algorithms and Data Structures: Heapsort
• Heapsort implementován ve 12 jazycích
• Řazení přehodnotil Paul Hsieh
• Prezentace v PowerPointu, která ukazuje, jak funguje třídění haldy, které je pro pedagogy.
• Otevřené datové struktury - Oddíl 11.1.3 - Heap -Sort , Pat Morin