Halda je často používaná datová struktura, která slouží k rychlému hledání minima. Dostaneme $n$ prvků a chceme najít nejmenší z nich, tedy jejich minimum.

Pokud hledáme jen jeden nejmenší prvek, tak ho najdeme průchodem všech prvků. V každém kroku porovnáme procházený prvek s dosud nalezeným minimem. Pokud je procházený prvek menší, tak jsme nalezli nové dosavadní minimum. V podsekci o časové složitosti jsme si ukázali, že je pro nalezení minima potřeba alespoň $n-1$ porovnání. Proto je hledání nejmenšího prvku pomocí průchodu nejlepším možným řešením.

Co když chceme najít i druhý nejmenší prvek? Nebo co když chceme najít $k$ nejmenších prvků?

Jednoduchým řešením je nalézt nejmenší prvek, odebrat ho z množiny prvků1 a ve zbývajících prvcích hledat minimum stejným způsobem. Tím dostaneme časovou složitost $\OO(kn)$.2 Můžeme najít následující nejmenší prvky rychleji?

Zajímavý nápad je rozdělit si zadaná čísla na dvě části o $n_1$ a $n_2$ prvcích. Na $n_1-1$ porovnání najdeme minimum v první části a na $n_2-1$ porovnání ve druhé. Porovnáním minim z obou částí najdeme minimum ze všech $n$ čísel. Celkem jsme potřebovali $n_1-1 + n_2-1+1 = n-1$ porovnání. Jak teď najít druhý nejmenší prvek? V jedné části minimum známe, ve druhé ho budeme muset znova spočítat. Pokud jsou části stejně velké, tak už druhé nejmenší číslo najdeme na nejvýše $\lceil n/2 \rceil + 1$ porovnání. Celkem jsme dvě nejmenší čísla nalezli na nejvýše $\lceil 3n/2\rceil$ porovnání.

Můžete navrhnout, že celou myšlenku můžeme zopakovat i v každé části. Rozdělením obou částí dostaneme čtyři nové části. Ty můžeme zase dále dělit a to tak dlouho, dokud části nejsou jednoprvkové. Tím dostaneme datovou strukturu, které se říká halda. Při práci s haldou používáme i další užitečné operace: přidávání nových prvků, mazání prvků a podobně.

Ještě než přistoupíme k samotné definici, tak jeden problém pro vás. Dostanete $n$ prvků. Jak rychle najdete $\sqrt{n}$ nejmenších z nich? Zvládli byste to v čase $\OO(\sqrt{n})$? (viz. cvičení)