Datová struktura je nějaký obecný programátorský výtvor pro rychlou práci s daty. Taková představa velmi dobře sedí objektovému programování: datová struktura se obvykle v programu bude vyskytovat jakožto objekt a když budeme chtít s jejími daty pracovat, budeme k tomu používat její metody. Zatím jsme se setkali například se zásobníkem a frontou: to jsou obojí datové struktury, ač poměrně stupidní.
Halda je datová struktura, která má přinejmenším operace vlož prvek (též insert) a vytáhni nejmenší (též extractMin). Haldu vytvoříme jako prázdnou a za běhu programu do ní vkládáme nějaké prvky, které jdou vzájemně porovnat. Podle potřeby také z haldy prvky odebíráme, a to vždy ten nejmenší, který zrovna halda obsahuje. Samozřejmě zrovna tak můžeme mít haldu, která bude rychle nabízet svůj největší prvek, ale už není tak snadné, kdyby měla umět obojí zároveň.
Není to nezbytně nutné, ale obvykle halda používá pro uspořádání svého obsahu zakořeněný strom, jehož každý vrchol je jeden prvek haldy (základní pojmy o grafech najdete v poznámkách z dřívějška). My si vystačíme navíc s haldou binární, tedy každý vrchol jejího stromu má nejvýše dva syny. Aby byl k něčemu užitečný, zavedeme si haldové pravidlo, že otec je vždy menší než každý z jeho synů. Díky tomu zákonitě nejmenší prvek musí být vždy na vrchu haldy, to znamená kořen.
Zatím neřešme, jak takový strom bude doopravdy v programu zapsaný, berme jej jen jako graf. Když máme do haldy vložit prvek, zavěsíme jej do poslední vrstvy stromu jako nový list. Musíme ale dát pozor, jestli jsme neporušili haldové pravidlo: pokud je menší než vlastní otec, prohodíme obsah těchto dvou vrcholů mezi sebou a případně zkontrolujeme opět otce o patro výš. Přinejhorším se takhle prvek dostane po logaritmicky mnoha výměnách až do kořene, časová složitost vkládání je tedy O(log(N)), kde N je počet prvků, které jsou v daný okamžik v haldě.
Při odebírání nejmenšího prvku, samozřejmě, nejdřív vezmeme obsah kořene a navrátíme jej uživateli. Musíme zaplnit volné místo, co po něm zůstalo, ale přitom dávat pozor, abychom tím nevytvořili díru někde uvnitř stromu: bude se nám to hodit obzvlášť pro haldu pracující s jedním polem. Ze stromu utrhneme tedy vždy její poslední list (tzn. ten, co je nejvíc vpravo) a jeho obsah dáme do kořene. Jistě je tenhle prvek větší něž jeden z jeho synů. Haldové pravidlo zajistíme tak, že jej vyměníme s tím menším z nich obou; pak opět ověříme, jestli oba synové vrcholu, do kterého jsme se dostali, už jsou v pořádku. Přinejhorším prvek skončí jako list, což by trvalo zase logaritmicky dlouho vzhledem k N.
Někdy se nám může hodit halda, která bude umět víc takových podobných operací. Můžete si například rozmyslet, že z naší haldy lze v logaritmickém čase odebírat i libovolný jiný prvek, pokud víme, kde přesně se v ní nachází.
Heapsort, čili třídení haldou, je vlastně jen předělané třídění přímým výběrem, když máme k dispozici haldu. Všechny prvky na vstupu vložíme nejdřív do haldy a potom jeden po druhém vyndáme, takže budou rovnou seřazené od nejmenšího po největší. Časová složitost sice závisí na tom, jak rychle pracuje použitá halda, ale prakticky vždy je to O(N·log(N)): lepší být nemůže (to se dá formálně dokázat) a horší by asi nebyla k ničemu dobrá.
Všechny prvky haldy uložíme do jednoho pole v pořadí, v jakém jsou ve stromu: po vrstvách od kořene dolů. Díky tomu, že vrcholy vždy přidáváme na konec a při odebírání trháme vždy úplně poslední list, nebudeme mít v poli žádné mezery a obsah haldy tedy bude zabírat opravdu jen prvních N míst v poli.
Elegantní trik je v tom, že si už nemusíme pamatovat o stromu nic dalšího: jeho struktura je daná přímo tím, jak jsou prvky za sebou uspořádané v poli. Víme, že i-tá vrstva obsahuje právě 2i-1 prvků, takže z indexu každého prvku v poli si můžeme jednoznačně spočítat, kde je v poli jeho otec a jeho synové. Kdybychom měli pole indexované od 1 do N, synové každého k-tého vrcholu mají indexy 2·k a (2·k)+1; otec má index k/2, zaokrouhleno dolů. Netřeba formálně dokazovat, stačí nakreslit si to na papír.
Zde jsou pro úplnost obě zmíněné operace zapsané v Pythonu. Protože pole je ve skutečnosti indexované od 0 do N-1, musíme na správných místech k indexu přičítat nebo odečítat jedničku; určitě je ale jednodušší ty výpočty pokaždé vymyslet, než se pokoušet všechny si je zapamatovat.
def heap_insert(pole, prvek):
pole.append(prvek)
novy = len(pole) - 1 # index nove pridaneho prvku
while novy > 0: # dokud se nedostaneme do korene
otec = (novy-1) // 2;
if pole[otec] < pole[novy]:
# vsechno je v poradku
break
pole[novy], pole[otec] = pole[otec], pole[novy]
novy = otec # a vyresime situaci o vrstvu vys
def heap_extract_min(pole):
vysledek = pole[0]
if len(pole) > 1:
# pokud v poli neco zbylo, musime ho zkontrolovat a opravit
pole[0] = pole.pop()
novy = 0;
while 2*novy + 2 < len(pole): # dokud ma prvek oba syny
levy_syn = 2*novy + 1
pravy_syn = 2*novy + 2
mensi_syn = levy_syn if pole[levy_syn] < pole[pravy_syn] else pravy_syn
if pole[novy] < pole[mensi_syn]:
# uz je vsechno v poradku
break
# jinak prvky prohodime
pole[novy], pole[mensi_syn] = pole[mensi_syn], pole[novy]
novy = mensi_syn # a vyresime situaci o vrstvu nize
if 2*novy + 2 == len(pole):
# specialni pripad, pokud ma prvek jen jedineho syna (a ten je tedy na konci pole)
levy_syn = 2*novy + 1
if pole[levy_syn] < pole[novy]:
pole[novy], pole[levy_syn] = pole[levy_syn], pole[novy]
return vysledek
# ukazkove pouziti: vlozime do haldy deset prvku a pak je jeden po druhem vytahneme
pole = list()
from random import randint
for i in range(10):
heap_insert(pole, randint(0, 100))
for i in range(10):
print(heap_extract_min(pole))
Asi nejčastěji se vyskytuje halda používající pro ukládání prvků jedno pole. Pokud má k dispozici jen pole neměnné délky, zabírá z něj přesto vždy jen tolik, kolik sama potřebuje: tedy indexy od 0 do N-1. Díky tomu si můžeme dovolit haldu mít přímo ve vstupním poli, pokud budeme dávat pozor, abychom jí včas uvolnili místo. Konkrétně, do ní budeme přidávat prvky jeden po druhém od začátku pole, po přidání každého prvku halda zabere v poli vždy to místo, které jsme zrovna uvolnili; zrovna tak si při odebírání můžeme dovolit ukládat prvky rovnou od konce pole, protože ten už halda nepotřebuje. Výsledek budeme mít potom seřazený od největšího po nejmenší, a zvládli jsme to jen s konstantním množstvím paměti navíc (nezávislým na velikosti vstupu): tomu se říká, že třídění pracuje in-place.
Občas (například pro Dijkstrův algoritmus) potřebujeme být schopní snížit hodnotu prvku, který už je v haldě. Může to porušit haldové pravidlo, kdybychom hodnotu snížili na méně než hodnotu jeho otce v haldě. Řešení ale už dobře známe: necháme dotyčný prvek vyplavat v haldě nahoru. Abychom věděli, kam do haldě sáhnout, musí si každý prvek pamatovat svůj index v poli. Operace decrease je pak jednoduchá:
def heap_decrease(pole, prvek):
index = prvek.index_v_halde
while index > 0: # dokud se nedostaneme do korene
otec = (index-1) // 2;
if pole[otec] < pole[index]:
break # vsechno je v poradku
pole[index], pole[otec] = pole[otec], pole[index]
pole[index].index_v_halde = index # puvodnimu otci jsme zmenili index
index = otec # a vyresime situaci o vrstvu vys
pole[index].index_v_halde = index
def heap_insert(pole, prvek):
pole.append(prvek)
prvek.index_v_halde = len(pole) - 1
heap_decrease(pole, prvek) # urcime index nove pridaneho prvku
Operace extract_min se ale o něco zesložití, protože každému přesunutému prvku musíme změnit index_v_halde. Asi je zbytečné ji rozepisovat, když to navíc není součást maturitní otázky.