Nastavení

• Binární strom s $h ≥ 1$ úplnými hladinami má $n = 2^0 + 2^1 + 2^2 + · · · + 2^h−1 = 2^h − 1$ vrcholů.

• Vzhledem ke tvaru haldy přibude nová hladina jen tehdy, když počet prvků $n$ vzroste z $2^h − 1$ na $2^h$.

• Z toho plyne vzorec, neboť právě funkce $⌊\log{n}⌋$ se právě při této změně $n$ zvětší o jedna a pro $n = 2^h − 1$ je počet hladin

  \begin{equation*} h = (h − 1) + 1 = ⌊\log{(2^h − 1)}⌋ + 1 \end{equation*}

$\square$

• Indukcí podle počtu vrcholů binárního stromu.

• Lemma platí triviálně pro $n = 3$ (2 listy a kořen − jediný vnitřní vrchol).

• Nechť $n > 3$ je liché. Odebráním posledního listu, který je druhým (tj. pravým) synem posledního vnitřního vrcholu, vznikne halda o sudé velikosti $n − 1$, pro kterou z ind. předp. lemma platí.

• Vrácením posledního listu se počet vnitřních vrcholů nezmění a původní strom jich tedy má $⌊(n − 1)/2⌋ = ⌊n/2⌋$.

• A počet listů se zvětší o jedna a původní strom jich tedy má $⌈(n − 1)/2⌉ + 1 = ⌈n/2⌉$.

• Nechť $n ≥ 4$ je sudé. Pak poslední list je jediný levý syn svého otce.

• Jeho odebráním vznikne halda liché velikosti $n − 1$, která má podle ind. předpokladu $⌈(n − 1)/2⌉$ listů a $⌊(n − 1)/2⌋$ vnitřních vrcholů.

• Vrácením posledního listu jeden vnitřní vrchol přibude a původní strom jich tedy má $⌊(n − 1)/2⌋ + 1 = ⌊n/2⌋$.

• A počet listů se nezmění a původní strom jich tedy má $⌈(n − 1)/2⌉ = ⌈n/2⌉$.

$\square$

Pokud $H$ je prázdná, pak je výsledkem jednoprvková halda – hotovo.

Jinak označme $\hat{H}$ výsledek volání HeapInsert $(H, k)$. $\hat{H}$ má dle (2) tvar haldy.

Zbývá ověřit, že splňuje podmínku haldového uspořádání.

Po přidání hodnoty k do nového listu $l$ může existovat jen jedna hrana s porušenou podmínkou.

Tento problém pomocí funkce BubbleUp posouváme směrem ke kořeni.

Je třeba ověřit, že nemůžeme porušit podmínku haldového uspořádání mezi nějakým otcem o a jeho (případným) druhým synem na cestě z $l$ do kořene.

• Pozorujeme, že hodnota k(o) v o se aplikováním BubbleUp nemohla zvýšit (může klesnout, případně zůstat stejná, pokud otec vrcholu o měl stejnou hodnotu).

$\square$

• Tvar haldy je opět zachován triviálně.

• Pokud je výsledkem prázdná či jednoprvková halda, máme hotovo.

• Prohození z (2) mohlo porušit haldové uspořádání (mezi hladinami 0 a 1).

• Opět prohazujeme s menším ze synů, čímž posunujeme porušení na dvojici následujících hladin.

• Toto může pokračovat jen do poslední hladiny.

$\square$

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

  \begin{equation*} \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 } ≤ n \sum_{q=0}^{h−1}{ \frac{q}{2^q} } \end{equation*}

• Časovou složitost lze shora odhadnout

  \begin{equation*} O(n\sum_{q=0}^{\infty}{\frac{q}{2^q}}) = O(n) \end{equation*}
  s použitím  d'Alembertova kritériua.

• Pro $a_k = \frac{k}{2^k}$ máme:

  \begin{equation*} \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\cdot 2} = \frac{1}{2} \end{equation*}

$\square$

Na každý vrchol na začátku položíme $p$ penízků. Co dělá každý prvek?

• Porovná se s menším ze synů (2 instrukce), může se s menším prohodit (1 instrukce) a pak se případně probublává dolů (směrem k listu).

• Ukážeme, že za toto zvládne „zaplatit“ jeden z podstromů.

• Když tedy nakonec přesuneme všechny zbylé penízky do kořene aktuálního stromečku, zbyde nám alespoň $p \cdot (k + 1)$ penízků, kde $k$ je vzdálenost kořenu uvažovaného stromečku od listů.

Důkaz proběhne indukcí podle $k$ – vzdálenosti od listu.

(Pro jednoduchost předpokládáme, že poslední hladina je zcela zaplněná – tím formálně ukazujeme $2pn$, ale není těžké důkaz poupravit.)

• ZI: $k = 0$. Triviálně platí, neboť neprovedeme žádné porovnání a na kontě zůstane $p = p(k + 1)$.

• IK: $k - 1 \rightarrow k$. Máme „nový kořen“ ve stromě $T$ a předpokládáme, že podstromy $T_\ell$ a $T_r$ jsou korektně vytvořeny a že (IP) každý z jejich kořenů má na kontě $pk$. Hloubka stromu $T$ je $k + 1$. Všimli jsem si, že v nejhorším případě uděláme s novým prvkem na každé hladině (kromě poslední) 3 operace. Celkově tedy za „opravení“ stromu $T$ zaplatíme $3k$. Na konci nám tedy zbyde $z = p + 2pk − 3k$. Pokud zvolíme $p \geq 3$, bude jistě $z \geq p(k + 1)$.

$\square$