Skip to content

4.5 Heap Build a Sort

Rychlá konstrukce haldy - operace HeapBuild

  • Haldu z n prvků lze vytvořit z prázdné haldy n voláními operace HeapInsert, což dává čas (pomocí Stirlingova vzorce)
\[O(log(2)) +O(log(3)) + ··· + O(log\ n) = O(log(n!)) \approx O(n\ log\ n)\]
  • Jde to však rychleji.

Algoritmus 4.3 (HeapBuild)

Algoritmus HeapBuild

Konstrukce haldy HeapBuild

Vstup

  • prvky \(x_1,...x_n\)

Výstup

  • Halda \(H[1...n]\)

Idea

  1. Má-li prvek \(v\) dva syny \(l\) a \(r\), kteří jsou kořeny podstromů tvořících již korektní haldy, lze podstrom s kořenem ve \(v\) předělat na haldu „zabubláním“ klíče \(k(v)\) dolů.
  2. Všech ⌈n/2⌉ listů jsou 1prvkové haldy.

Algoritmus

Algoritmus HeapBuild:
1
2
3
    vlož prvky do pole H tak, že H[i] := xi
    Pro i := ⌊n/2⌋, . . . , 1:
        BubbleDown(H[i])

Věta 4.5 (O časové složitosti algoritmu HeapBuild)

O časové složitosti HeapBuild

Operace HeapBuild má časovou složitost \(O(n)\).

Důkaz Věty 4.5
  • Nechť strom haldy má \(h\) hladin (od 0 do h-1)
  • Platí tedy \(2^{h-1} \le n \le 2^h - 1\).
  • Pro účely analýzy si představíme, že i poslední hladina je zcela plná, například nějakými „dummy“ prvky většími než vše ostatní, tím jistě nesnížíme potřebný počet operací.
  • Procedura BubbleDown od \(j\)-té hladiny trvá čas \(O(h − 1 − j)\).
  • Pokud to sečteme přes všech \(2^j\) vrcholů hladiny \(j\) a poté přes všechny hladiny, dostaneme (až na konstantu)
\[\sum_{j=0}^{h-1}2^j(h - 1 - j) = \sum_{q=0}^{h-1}2^{h-1-q}q = \sum_{q=0}^{h-1} \frac{2^{h-1}}{2^q}q \le n\sum_{q=0}^{h-1}\frac{q}{2^q}\]

Věta (d’Alembertovo kritérium – BI-MA2)

Nechť \(a_k \gt 0\) pro každé \(k \in \mathbb{N}\). Pokud \(\lim_{k\to\infty} \frac{a_{k+1}}{a_k} \lt 1\), potom řada \(\sum_{k=0}^{\infty}a_k\) absolutně konverguje.

  • Časovou složitost lze shora odhadnout \(O(n\sum_{q=0}^{\infty}\frac{q}{2^q}) = O(n).\)
  • Pro \(a_k = \frac{k}{2^k}\) máme:
\[\lim_{k\to\infty}\frac{k+1}{2^{k+1}}/\frac{k}{2^k} = lim_{k\to\infty}\frac{(k + 1) \cdot 2^k}{k \cdot 2^{k+1}} = lim_{k\to\infty}\frac{k+1}{k\cdot2} = \frac{1}{2}\]
  • Navíc \(\frac{k}{2^k} \gt 0\), takže jsou splněny předpoklady d’Alemebrtova kritéria a proto řada \(\sum a_k\) konverguje k nějaké kladné reálné konstantě \(c\) a tedy: \(O(n \sum q/{2^q}) = O(c \cdot n) = O(n)\).

HeapSort

Algoritmus 4.4 (HeapSort)

Algoritmus HeapSort

Halda umožňuje zkonstruovat rychlý algoritmus pro řazení Heapsort

Vstup

  • pole \(p = [x_1,...x_n]\)

Výstup

  • seřazené pole \(p\)

Idea

  1. Prvky \(x_1,...,x_n\) vložíme do pole.
  2. Na toto pole zavoláme HeapBuild.
  3. Poté \(n\)-krát zavoláme HeapExtractMin a vracené hodnoty vypíšeme do výstupního pole. Tím vygenerujeme vzestupně seřazenou posloupnost.

Časová složitost

Podle předchozích analýz má HeapSort časovou složitost \(O(n) + O(n\ log\ n) = O(n\ log\ n)\).

K Zamyšlení

  • Předchozí popis algoritmu HeapSort předpokládal, že se odebíraná minima postupně zapisují do výstupního pole.
  • Jedná se tedy o efektivnější realizaci myšlenky algoritmu SelectSort.
  • Algoritmus HeapSort lze realizovat in-place, tedy bez použití extra paměti na uložení zkonstruované haldy.
  • Navrhněte, jak to provést, když vstupní posloupnost je uložena v poli \(P\) a kromě tohoto pole smíte použít již jen \(O(1)\) pomocných proměnných.