4.2 Vlastnosti haldy

Počet hladin haldy

Věta 4.1 (O počtu hladin haldy)

Binární halda s \(n\) prvky má \(\lfloor log(n) \rfloor + 1\) hladin.

Důkaz Věty 4.1

Binární strom s \(h \ge 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 \(\lfloor log(n) \rfloor\) se právě při této
změně \(n\) zvětší o jedna a pro \(n=2^h - 1\) je počet hladin
\(h = (h - 1) + 1 = \lfloor log(2^h - 1) \rfloor + 1\).

Věta 4.2 (O počtu listů haldy)

Binární halda s \(n \ge 3\) prvky má \(\lfloor n/2 \rfloor\) vnitřních vrcholů a \(\lceil n/2 \rceil\) listů.

Důkaz Věty 4.2

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 \gt 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á \(\lfloor (n-1)/2 \rfloor = \lfloor n/2 \rfloor\)
A počet listů se zvětší o jedna a původní strom jich tedy má \(\lceil (n-1)/2 \rceil + 1 = \lceil n/2 \rceil\)
Nechť \(n \ge 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 \(\lceil (n − 1)/2 \rceil\) listů a \(\lfloor (n − 1)/2 \rfloor\) vnitřních vrcholů.
Vrácením posledního listu jeden vnitřní vrchol přibude a původní strom jich tedy má \(\lfloor (n − 1)/2 \rfloor + 1 = \lfloor n/2 \rfloor\).
A počet listů se nezmění a původní strom jich tedy má \(\lceil (n − 1)/2 \rceil = \lceil n/2 \rceil\).