A Halda je speciál kompletní binární strom . Protože halda je úplný binární strom, halda s N uzly má log N výška. Je užitečné odstranit prvek s nejvyšší nebo nejnižší prioritou. Obvykle je reprezentován jako an pole . Existují dva typy haldMin-Hromad
jádro poruchy segmentace vyhozeno
V Min-Hromad klíč přítomný v kořenovém uzlu musí být menší nebo stejný mezi klíči přítomnými u všech jeho potomků. Stejná vlastnost musí být rekurzivně pravdivá pro všechny podstromy v tomto binárním stromu. V Min-Heap minimální klíčový prvek přítomný v kořenu. Níže je Binární strom, který splňuje všechny vlastnosti Min Heap.
Max Heap
V Max-Hroma klíč přítomný v kořenovém uzlu musí být větší nebo stejný mezi klíči přítomnými u všech jeho potomků. Stejná vlastnost musí být rekurzivně skutečný pro všechny podstromy v tomto binárním stromu. V Max-Heap maximální klíčový prvek přítomný v kořenovém adresáři. Níže je binární strom, který splňuje všechny vlastnosti Max Heap.
Rozdíl mezi minimální haldou a maximální haldou
| Min. halda | Max Heap | |
|---|---|---|
| 1. | V Min-Heap musí být klíč přítomný v kořenovém uzlu menší nebo roven mezi klíči přítomnými u všech jeho potomků. | V Max-Heap musí být klíč přítomný v kořenovém uzlu větší nebo roven mezi klíči přítomnými u všech jeho potomků. |
| 2. | V Min-Heap minimální klíčový prvek přítomný v kořenu. | V Max-Heap maximální klíčový prvek přítomný v kořenovém adresáři. |
| 3. | Min-Heap používá vzestupnou prioritu. | Max-Heap používá sestupnou prioritu. |
| 4. | Při konstrukci min-hromady má přednost nejmenší prvek. | Při konstrukci Max-Heap má největší prvek přednost. |
| 5. | V Min-Heap je nejmenší prvek první, který je vytažen z hromady. | V Max-Heap je největší prvek první, který je vytažen z hromady. |
Aplikace hald :
- Řazení haldy : Heap Sort je jedním z nejlepších třídicích algoritmů, které se používají Binární halda na seřadit pole v O(N*log N) čas.
- Prioritní fronta : Prioritní frontu lze implementovat pomocí haldy, protože podporuje vložit() , vymazat() , extraktMax() , snížitKey() operace v O(log N) čas.
- Dijkstrova nejkratší cesta a Primův minimální kostra .
Analýza výkonnosti Min-Heap a Max-Heap :
- Získat maximální nebo minimální prvek: O(1)
- Vložit prvek do maximální haldy nebo minimální haldy: O (log N)
- Odebrat maximální nebo minimální prvek: O (log N)