11-Trideni_halda_stromy
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
jednoduše pomocí pole.
• Uzlům přiřadíme indexy 0,1, … , 𝑛 − 1.
• Indexy přiřazujeme po vrstvách shora dolů, v každé hladině zleva doprava.
Implementace haldy pomocí pole
9
3
7
1
8
4
5
2
[0]
[1]
[3]
[2]
[4]
[5]
[6]
[7]
9
5
7
4
2
3
8
1
[0] [1] [2] [3] [4] [5] [6] [7]
Implementace haldy pomocí pole
• Má-li uzel index 𝑖, pak jeho levý následník má index 2𝑖 + 1 a pravý
následník index 2𝑖 + 2.
• Předchůdce uzlu 𝑖 pro 𝑖 > 0 má index 𝑖 − 1 /2, přičemž 𝑖 𝑚𝑜𝑑 2
nám řekne, zda je uzel připojen k předchůdci levou nebo pravou
stranou (tj. zda je levým nebo pravý následníkem).
Složitost metody třídění pomocí haldy
• Výsledná složitost metody je pro libovolnou posloupnost: 𝑛 ∙ 𝑙𝑜𝑔2 𝑛