Halda

Z CHWiki

http://tutchek.igroup.cz/wiki/halda-ico.jpg (angl. Heap)

Obsah 1 Popis 2 Složitost 3 Algoritmy 3.1 Min 3.2 Insert 3.3 Delete 4 Implementace

[editovat] Popis

Halda je datová struktura vhodná pro hledání minima/maxima dané množiny. Zde budeme mluvit pouze o haldě s minimem, druhý typ vznikne obdobně.

Halda je reprezentována binárním stromem, kde pro každý uzel x platí: hodnota(x) > hodnota(rodič(x))

http://tutchek.igroup.cz/wiki/halda-nahled.gif

[editovat] Složitost

• Hledání minima O(1)
• Vkládání prvku do haldy O(lg(n))
• Odebrání minima z haldy O(lg(n))

[editovat] Algoritmy

[editovat] Min

Minimum je v kořeni stromu.

[editovat] Insert

Vkládáme uzel x:

1. Připojíme x jako list, na konec poslední hladiny.
2. Pokud platí x je kořen nebo hodnota(x) > hodnota(rodič(x)) skončíme.
3. Jinak prohodíme x a rodič(x).
4. Pokračujeme krokem 2.

Ukázka: Insert - x=3:

http://tutchek.igroup.cz/wiki/halda-insert0.gif

http://tutchek.igroup.cz/wiki/halda-insert1.gif

http://tutchek.igroup.cz/wiki/halda-insert2.gif

[editovat] Delete

Odebíráme kořen:

1. Odebereme kořen.
2. Označme x poslední list zleva na poslední hladině. X umístíme do kořene.
3. Pokud platí x je list a nebo hodnota(x) < hodnota(levý_syn(x)) a hodnota(x) < hodnota(pravý_syn(x)) skončíme.
4. Prohodíme x a menšího ze synů tzn. min(hodnota(levý_syn(x)), hodnota(pravý_syn(x)))
5. Pokračujeme krokem 3.

Ukázka:

http://tutchek.igroup.cz/wiki/halda-delete0.gif

http://tutchek.igroup.cz/wiki/halda-delete1.gif

http://tutchek.igroup.cz/wiki/halda-delete2.gif

http://tutchek.igroup.cz/wiki/halda-delete3.gif

[editovat] Implementace

Běžná implementace haldy je v poli. V tom případě má prvek s indexem I levého syna na prvku s indexem 2I a pravého syna na prvku s indexem 2I+1. Rodič má index I div 2.

Ukázka:

Aktivní uzel - I=7, předek Ip = 7 div 2 = 3, levý syn ILS = 7 * 2 = 14, pravý syn IPS = 7 * 2 + 1 = 15

http://tutchek.igroup.cz/wiki/halda-pole.gif

Poslední list v operaci insert a delete je zde reprezentován posledním obsazeným prvkem pole.