A Högen är en speciell komplett binärt träd . Eftersom en hög är ett komplett binärt träd, en hög med N noder har log N höjd. Det är användbart att ta bort det högsta eller lägsta prioritetselementet. Det representeras vanligtvis som en array . Det finns två typer av heaps iMin-Hög
I en Min-Hög nyckeln som finns vid rotnoden måste vara mindre än eller lika med nycklarna som finns på alla dess underordnade. Samma egenskap måste vara rekursivt sann för alla underträd i det binära trädet. I en Min-Heap det minsta nyckelelementet som finns vid roten. Nedan är det binära trädet som uppfyller Min Heaps alla egenskaper.
skillnaden mellan kärlek och tycke
Max Heap
I en Max-Heap nyckeln som finns vid rotnoden måste vara större än eller lika med nycklarna som finns på alla dess underordnade. Samma egenskap måste vara rekursivt Sann för alla underträd i det binära trädet. I en Max-Heap det maximala nyckelelementet som finns vid roten. Nedan är det binära trädet som uppfyller alla egenskaper hos Max Heap.
Skillnaden mellan Min Heap och Max Heap
| Min hög | Max Heap | |
|---|---|---|
| 1. | I en Min-Heap måste nyckeln som finns vid rotnoden vara mindre än eller lika med bland nycklarna som finns hos alla dess underordnade. | I en Max-Heap måste nyckeln som finns vid rotnoden vara större än eller lika med bland nycklarna som finns hos alla dess underordnade. |
| 2. | I en Min-Heap det minsta nyckelelementet som finns vid roten. | I en Max-Heap det maximala nyckelelementet som finns vid roten. |
| 3. | En Min-Heap använder stigande prioritet. | En Max-Heap använder den fallande prioriteten. |
| 4. | I konstruktionen av en Min-Heap har det minsta elementet prioritet. | Vid konstruktionen av en Max-Heap har det största elementet prioritet. |
| 5. | I en Min-Heap är det minsta elementet det första som tas bort från högen. | I en Max-Heap är det största elementet det första som tas bort från högen. |
Tillämpningar av Heaps :
- Hög sortering : Heap Sort är en av de bästa sorteringsalgoritmerna som används Binär hög till sortera en array i O(N*log N) tid.
- Prioriterad kö : En prioritetskö kan implementeras genom att använda en heap eftersom den stöder Föra in() , radera() , extraheraMax() , minskaKey() verksamhet i O(log N) tid.
- Dijkstras kortaste väg och Prims minsta utvidgningsträd .
Prestandaanalys av Min-Heap och Max-Heap :
- Få högsta eller lägsta element: O(1)
- Infoga element i Max-Heap eller Min-Heap: O(log N)
- Ta bort max- eller minimumelement: O(log N)