Vyrobiť haldu obsahujúcu daných $n$ prvkov vieme aj efektívnejšie ako postupným vkladaním prvkov do pôvodne prázdnej haldy. Použitím jednoduchého triku dokážeme binárnu haldu vyrobiť v lineárnom čase.
Majme pole obsahujúce našich $n$ prvkov. Na toto pole sa môžeme dívať ako na takmer úplný binárny strom, v ktorom len potrebujeme preusporiadať prvky tak, aby všade platila podmienka haldy. Ukážeme, že na to, aby sme ju zabezpečili, stačí v správnom poradí bublať jej prvkami dodola.
Presnejšie, budeme prvky spracúvať od konca poľa, t. j. od listov haldy. Pre každý z nich zoberieme hodnotu, ktorá v ňom aktuálne je, a prebubleme ňou dodola, kým to ide.
Prečo to funguje?
Stačí si všimnúť, že vždy v okamihu, kedy spracujeme niektorý vrchol, platí, že celý podstrom daného vrcholu už spĺňa podmienku haldy. (Keď spracúvame nejaký vrchol, znamená to, že už sme predtým spracovali oboch jeho synov, a teda ich podstromy už oba spĺňajú podmienku haldy. Máme teda starú známu situáciu, kedy jedine hodnota v koreni aktuálneho podstromu kazí podmienku haldy v ňom, no a bublaním tejto hodnoty dodola tento kaz odstránime.)
A zaujímavejšia otázka: Ako rýchlo to funguje?
Celkovú časovú zložitosť vieme odhadnúť ako počet spracovaných vrcholov plus celkový počet krokov bublania dodola. Počet spracovaných vrcholov je $n$. Celkový počet krokov bublania dodola odhadneme nasledujúcou úvahou:
Predstavme si, že sme nechali prebehnúť náš algoritmus. Všimnime si teraz ľubovoľnú konkrétnu úroveň $x$ v našej halde a položme si otázku: Koľkokrát sa stalo, že na túto úroveň klesol niektorý prvok? Zjavne keď pre každú úroveň spočítame počet prvkov, ktoré na ňu niekedy klesli, dostaneme presne celkový počet krokov bublania dodola.
No a na druhej strane na úroveň $x$ mohli klesnúť len prvky, ktoré pôvodne boli na vyšších úrovniach. A tých bolo presne 2x−1.
Preto celkový počet krokov bublania dodola v halde s hĺbkou $k$ je nanajvýš rovný $(2^k−1)+(2^{k−1}−1)+\dots+(2^1−1)=2^{k+1}−k−2$
No a pre počet vrcholov $n$ haldy s hĺbkou k platí $n\geq2^k$. A teda celkový počet krokov bublania dodola je menší ako $2n$.