A Krūva yra ypatingas pilnas dvejetainis medis . Kadangi krūva yra pilnas dvejetainis medis, krūva su N mazgai turi log N aukščio. Naudinga pašalinti aukščiausio arba mažiausio prioriteto elementą. Paprastai jis vaizduojamas kaip masyvas . Yra dviejų tipų krūvosMin-Heap
A Min-Heap šakniniame mazge esantis raktas turi būti mažesnis arba lygus visuose antriniuose raktuose. Ta pati savybė turi būti rekursyviai teisinga visiems to dvejetainio medžio submedžiams. Min-Heap minimalus pagrindinis elementas, esantis šaknyje. Žemiau yra dvejetainis medis, kuris patenkina visą Min Heap nuosavybę.
Max Heap
A Max-Heap šakniniame mazge esantis raktas turi būti didesnis arba lygus visuose jo antriniuose raktuose. Ta pati nuosavybė turi būti rekursyviai tiesa visiems to dvejetainio medžio pomedžiams. Max-Heap didžiausias pagrindinis elementas, esantis šaknyje. Žemiau yra dvejetainis medis, kuris atitinka visas Max Heap savybes.
Skirtumas tarp Min Heap ir Max Heap
| Min. krūva | Max Heap | |
|---|---|---|
| 1. | Min-Heap raktas, esantis šakniniame mazge, turi būti mažesnis arba lygus tarp visų antrinių raktų. | „Max-Heap“ šakniniame mazge esantis raktas turi būti didesnis arba lygus tarp visų antrinių raktų. |
| 2. | Min-Heap minimalus pagrindinis elementas, esantis šaknyje. | Max-Heap didžiausias pagrindinis elementas, esantis šaknyje. |
| 3. | Min-Heap naudoja didėjantį prioritetą. | Max-Heap naudoja mažėjantį prioritetą. |
| 4. | Konstruojant „Min-Heap“ pirmenybė teikiama mažiausiam elementui. | „Max-Heap“ konstrukcijoje pirmenybė teikiama didžiausiam elementui. |
| 5. | Min-Heap mažiausias elementas yra pirmasis, kuris iškeliamas iš krūvos. | Max-Heap didžiausias elementas yra pirmasis, kuris ištraukiamas iš krūvos. |
Krūvos taikymas :
- Krūvos rūšiavimas : Heap Sort yra vienas geriausių naudojamų rūšiavimo algoritmų Dvejetainė krūva į rūšiuoti masyvą in O (N*log N) laikas.
- Prioritetinė eilė : Prioritetinė eilė gali būti įdiegta naudojant krūvą, nes ji palaiko Įdėti() , Ištrinti() , ExtractMax() , MažinimoKey() operacijos O(log N) laikas.
- Dijkstros trumpiausias kelias ir Prim minimalus besitęsiantis medis .
Min-Heap ir Max-Heap našumo analizė :
suderinamumo bandymas
- Gaukite didžiausią arba mažiausią elementą: O(1)
- Elemento įterpimas į Max-Heap arba Min-Heap: O(log N)
- Pašalinti didžiausią arba mažiausią elementą: O (log N)