A Hoop is een bijzonder volledige binaire boom . Omdat een heap een volledige binaire boom is, kan een heap met N knooppunten heeft log N hoogte. Het is handig om het element met de hoogste of laagste prioriteit te verwijderen. Het wordt doorgaans weergegeven als een reeks . Er zijn twee soorten Heaps in deMin-hoop
In een Min-hoop de sleutel die aanwezig is op het hoofdknooppunt moet kleiner zijn dan of gelijk zijn aan de sleutels die aanwezig zijn op al zijn onderliggende knooppunten. Dezelfde eigenschap moet recursief waar zijn voor alle subbomen in die binaire boom. In een Min-Heap het minimale sleutelelement dat aanwezig is in de root. Hieronder vindt u de binaire boom die voldoet aan alle eigendommen van Min Heap.
Max Hoop
In een Max-hoop de sleutel die aanwezig is bij het hoofdknooppunt moet groter zijn dan of gelijk zijn aan de sleutels die aanwezig zijn bij al zijn kinderen. Het moet dezelfde eigenschap zijn recursief WAAR voor alle subbomen in die binaire boom. In een Max-Heap het maximale sleutelelement dat aanwezig is in de root. Hieronder vindt u de binaire boom die voldoet aan alle eigendommen van Max Heap.
mijnflixr
Verschil tussen Min Heap en Max Heap
| Min hoop | Max Hoop | |
|---|---|---|
| 1. | In een Min-Heap moet de sleutel die aanwezig is op het hoofdknooppunt kleiner zijn dan of gelijk zijn aan de sleutels die aanwezig zijn op alle onderliggende knooppunten. | In een Max-Heap moet de sleutel die aanwezig is op het hoofdknooppunt groter zijn dan of gelijk zijn aan de sleutels die aanwezig zijn op alle onderliggende knooppunten. |
| 2. | In een Min-Heap het minimale sleutelelement dat aanwezig is in de root. | In een Max-Heap het maximale sleutelelement dat aanwezig is in de root. |
| 3. | Een Min-Heap gebruikt de oplopende prioriteit. | Een Max-Heap gebruikt de aflopende prioriteit. |
| 4. | Bij de constructie van een Min-Heap heeft het kleinste element prioriteit. | Bij de constructie van een Max-Heap heeft het grootste element prioriteit. |
| 5. | In een Min-Heap wordt het kleinste element als eerste uit de hoop gehaald. | In een Max-Heap wordt het grootste element als eerste uit de hoop gehaald. |
Toepassingen van hopen :
- Hoop sorteren : Heap Sort is een van de beste sorteeralgoritmen die worden gebruikt Binaire hoop naar sorteer een array in O(N*log N) tijd.
- Prioriteits-rij : Een prioriteitswachtrij kan worden geïmplementeerd door een heap te gebruiken, omdat deze deze ondersteunt invoegen() , verwijderen() , extraheerMax() , sleutel verlagen() operaties in O(log N) tijd.
- Dijkstra's kortste pad En Prim's minimale spanningsboom .
Prestatieanalyse van Min-Heap en Max-Heap :
- Verkrijg maximaal of minimaal element: O(1)
- Element invoegen in Max-Heap of Min-Heap: O(log N)
- Maximaal of minimaal element verwijderen: O(log N)