A Hromada je špeciálna úplný binárny strom . Keďže halda je úplný binárny strom, halda s N uzly má denník N výška. Je užitočné odstrániť prvok s najvyššou alebo najnižšou prioritou. Typicky je reprezentovaný ako pole . Existujú dva typy hromady vMin-Hroma
V Min-Hroma kľúč prítomný v koreňovom uzle musí byť menší alebo rovnaký medzi kľúčmi prítomnými vo všetkých jeho potomkoch. Rovnaká vlastnosť musí byť rekurzívne pravdivá pre všetky podstromy v tomto binárnom strome. V Min-Heap je minimálny kľúčový prvok prítomný v koreňovom adresári. Nižšie je binárny strom, ktorý spĺňa všetky vlastnosti Min Heap.
Max Heap
V Max-Heap kľúč prítomný v koreňovom uzle musí byť väčší alebo rovnaký medzi kľúčmi prítomnými vo všetkých jeho potomkoch. Musí byť rovnaká vlastnosť rekurzívne pravda pre všetky podstromy v tomto binárnom strome. V Max-Heap je maximálny kľúčový prvok prítomný v koreňovom adresári. Nižšie je binárny strom, ktorý spĺňa všetky vlastnosti Max Heap.
Rozdiel medzi Min Heap a Max Heap
| Min. halda | Max Heap | |
|---|---|---|
| 1. | V Min-Heap kľúč prítomný v koreňovom uzle musí byť menší alebo rovný medzi kľúčmi prítomnými u všetkých jeho potomkov. | V Max-Heap kľúč prítomný v koreňovom uzle musí byť väčší alebo rovný medzi kľúčmi prítomnými vo všetkých jeho potomkoch. |
| 2. | V Min-Heap je minimálny kľúčový prvok prítomný v koreňovom adresári. | V Max-Heap je maximálny kľúčový prvok prítomný v koreňovom adresári. |
| 3. | Min-Heap používa vzostupnú prioritu. | Max-Heap používa zostupnú prioritu. |
| 4. | Pri konštrukcii min-hromady má prednosť najmenší prvok. | Pri konštrukcii Max-Heap má prednosť najväčší prvok. |
| 5. | V Min-Heap je najmenší prvok prvý, ktorý sa vysype z haldy. | V Max-Heap je najväčší prvok prvý, ktorý sa vysype z haldy. |
Aplikácie Heaps :
- Hromadné triedenie : Heap Sort je jedným z najlepších triediacich algoritmov, ktoré sa používajú Binárna halda do zoradiť pole v O(N*log N) čas.
- Prioritný front : Prioritný front môže byť implementovaný pomocou haldy, pretože podporuje vložiť() , vymazať () , extraktMax() , znížiť kľúč() operácie v O (log N) čas.
- Dijkstrova najkratšia cesta a Primov minimálny kostrový strom .
Analýza výkonnosti Min-Heap a Max-Heap :
- Získať maximálny alebo minimálny prvok: O(1)
- Vložte prvok do maximálnej hromady alebo minimálnej hromady: O (log N)
- Odstrániť maximálny alebo minimálny prvok: O (log N)