Phenquestions
Illustratie van heap-gegevensstructuren
Er zijn twee soorten heaps: een max-heap en een min-heap. Een max-heap-structuur is waar de maximale waarde de wortel is en de waarden kleiner worden naarmate de boom daalt; elke ouder is gelijk aan of groter in waarde dan een van zijn directe kinderen. Een min-heap-structuur is waar de minimumwaarde de wortel is en de waarden groter worden naarmate de boom daalt; elke ouder is gelijk aan of kleiner in waarde dan een van zijn directe kinderen. In de volgende diagrammen is de eerste een max-heap en de tweede een min-heap:
Merk voor beide hopen op dat het voor een paar kinderen niet uitmaakt of de linker de grotere waarde heeft. Een rij in een niveau in de boom, hoeft niet noodzakelijkerwijs van minimum naar maximum te worden gevuld, van links; het is ook niet noodzakelijkerwijs gevuld van maximum naar minimum, van links.
Een hoop in een array vertegenwoordigen
Om software gemakkelijk een heap te laten gebruiken, moet de heap in een array worden weergegeven. De max-heap hierboven, weergegeven in een array, is:
89, 85, 87, 84, 82, 79, 73, 80, 81, , , 65, 69Dit wordt gedaan beginnend met de root-waarde als de eerste waarde voor de array. De waarden worden continu geplaatst door de boom van links naar rechts, van boven naar beneden af te lezen. Als een element afwezig is, wordt zijn positie in de array overgeslagen. Elke knoop heeft twee kinderen. Als een knoop zich op index (positie) n bevindt, is het eerste kind in de array index 2n+1 en het volgende kind index 2n+2. 89 staat op index 0; zijn eerste kind, 85 heeft index 2(0)+1=1 terwijl zijn tweede kind index 2(0)+2=2 heeft. 85 staat op index 1; het eerste kind, 84, heeft index 2(1)+1=3 terwijl het tweede kind, 82, index 2(1)+2=4 heeft. 79 staat op index 5; zijn eerste kind, 65 heeft index 2(5)+1=11 terwijl zijn tweede kind index 2(5)+2=12 heeft. De formules worden toegepast op de rest van de elementen in de array.
Een dergelijke array, waarbij de betekenis van een element en de relatie tussen de elementen wordt geïmpliceerd door de positie van het element, wordt een impliciete datastructuur genoemd.
De impliciete datastructuur voor de bovenstaande min-heap is:
65, 68, 70, 73, 71, 83, 84, , , 79, 80, , , 85, 89De bovenstaande max-heap is een volledige binaire boom, maar geen volledige binaire boom. Daarom zijn sommige locaties (posities) leeg in de array. Voor een volledige binaire boom is er geen locatie leeg in de array.
Als de heap nu een bijna volledige boom zou zijn, bijvoorbeeld als de waarde 82 ontbrak, dan zou de array zijn:
89, 85, 87, 84, , 79, 73, 80, 81, , , 65, 69In deze situatie zijn drie locaties leeg. De formules zijn echter nog steeds van toepassing.
Operaties
Een datastructuur is een dataformaat (e.g. een boom), plus de relatie tussen de waarden, plus de bewerkingen (functies) die op de waarden worden uitgevoerd. Voor een heap is de relatie die door de hele heap loopt, dat de ouder gelijk of groter in waarde moet zijn dan de kinderen, voor een max-heap; en de ouder moet gelijk zijn aan of minder waard zijn dan de kinderen, voor een min-heap. Deze relatie wordt de heap-eigenschap genoemd. De handelingen van een heap zijn gegroepeerd onder de kopjes Creatie, Basis, Intern en Inspectie. Een samenvatting van de operaties van de heap volgt:
Samenvatting van heapbewerkingen
Er zijn bepaalde softwarebewerkingen die veel voorkomen bij hopen, namelijk:
Creatie van een hoop
create_heap: Een heap maken betekent een object vormen dat de heap vertegenwoordigt. In de C-taal kun je een heap maken met het struct-objecttype. Een van de leden van de struct is de heap-array. De rest van de leden zullen functies (operaties) zijn voor de hoop. Create_heap betekent een lege heap maken.
Heapify: de heap-array is een gedeeltelijk gesorteerde (geordende) array. Heapify betekent, geef een heap-array uit een ongesorteerde array - zie details hieronder.
Samenvoegen: Dit betekent, vorm een unie-heap van twee verschillende heaps - zie details hieronder. De twee hopen moeten beide max-heap of beide min-heap zijn. De nieuwe heap is in overeenstemming met de heap-eigenschap, terwijl de originele heaps behouden blijven (niet gewist).
Meld: Dit betekent dat u twee hopen van hetzelfde type samenvoegt om een nieuwe te vormen, waarbij u duplicaten behoudt - zie details hieronder. De nieuwe heap is in overeenstemming met de heap-eigenschap, terwijl de originele heaps worden vernietigd (gewist). Het belangrijkste verschil tussen samenvoegen en samenvoegen is dat voor het samenvoegen de ene boom als een subboom past bij de wortel van de andere boom, waardoor dubbele waarden in de nieuwe boom mogelijk zijn, terwijl voor het samenvoegen een nieuwe heapboom wordt gevormd, waardoor duplicaten worden verwijderd. Het is niet nodig om de twee originele hopen te behouden met samensmelting.
Basis heapbewerkingen
find_max (find_min): zoek de maximale waarde in de max-heap-array en retourneer een kopie, of zoek de minimumwaarde in de min-heap-array en retourneer een kopie.
Invoegen: voeg een nieuw element toe aan de heap-array en herschik de array zodat de heap-eigenschap van het diagram behouden blijft.
extract_max (extract_min): Zoek de maximale waarde in de max-heap-array, verwijder en retourneer deze; of zoek de minimumwaarde in de min-heap-array, verwijder en retourneer deze.
delete_max (delete_min): Lokaliseer het hoofdknooppunt van een max-heap, het eerste element van de max-heap-array, verwijder het zonder het noodzakelijkerwijs terug te geven; of zoek het hoofdknooppunt van een min-heap, het eerste element van de min-heap-array, verwijder het zonder het noodzakelijkerwijs terug te geven;
Vervangen: Lokaliseer het hoofdknooppunt van een van beide heaps, verwijder het en vervang het door een nieuwe. Het maakt niet uit of de oude root wordt geretourneerd.
Interne heapbewerkingen
raise_key (decrease_key): Verhoog de waarde van een knooppunt voor een max-heap en herschikken zodat de heap-eigenschap behouden blijft, of verlaag de waarde van een willekeurig knooppunt voor een min-heap en herschikken zodat de heap-eigenschap behouden blijft.
Verwijderen: verwijder een willekeurig knooppunt en herschik vervolgens, zodat de heap-eigenschap behouden blijft voor de max-heap of een min-heap.
shift_up: verplaats een knooppunt in een max-heap of min-heap zo lang als nodig is, herschikken om de heap-eigenschap te behouden.
shift_down: verplaats een knooppunt naar beneden in een max-heap of min-heap zo lang als nodig is, herschikken om de heap-eigenschap te behouden.
Inspectie van een hoop
Grootte: Dit retourneert het aantal sleutels (waarden) in een heap; het omvat niet de lege locaties van de heap-array. Een heap kan worden weergegeven door code, zoals in het diagram, of met een array.
is leeg: Dit retourneert Booleaans waar als er geen knooppunt in een heap is, of Booleaans onwaar als de heap ten minste één knooppunt heeft.
Zeven op een hoop
Er is ziften en ziften:
Zeef: Dit betekent dat een knooppunt wordt verwisseld met zijn bovenliggende. Als niet aan de heap-eigenschap wordt voldaan, verwissel dan de ouder met zijn eigen ouder. Ga zo verder in het pad totdat aan de heap-eigenschap is voldaan. De procedure kan de root bereiken.
Zeef naar beneden: Dit betekent dat een knoop van grote waarde wordt verwisseld met de kleinste van zijn twee kinderen (of één kind voor een bijna volledige hoop). Als niet aan de eigenschap heap wordt voldaan, verwissel dan het onderste knooppunt met het kleinere knooppunt van zijn eigen twee kinderen. Ga zo verder in het pad totdat aan de heap-eigenschap is voldaan. De procedure kan een blad bereiken.
Ophopen
Heapify betekent een ongesorteerde array sorteren om aan de eigenschap heap te voldoen voor max-heap of min-heap. Dit betekent dat er enkele lege locaties in de nieuwe array kunnen zijn. Het basisalgoritme om een max-heap of min-heap te heapificeren is als volgt:
- als de root-node extremer is dan een van de onderliggende nodes, verwissel dan de root met de minder extreme child-node.
- Herhaal deze stap met de onderliggende knooppunten in een Pre-Order Tree Traversing Scheme.
De laatste boom is een heap tree die voldoet aan de heap eigenschap. Een heap kan worden weergegeven als een boomdiagram of in een array. De resulterende hoop is een gedeeltelijk gesorteerde boom, i.e. een gedeeltelijk gesorteerde array.
Details van heapoperatie
Dit gedeelte van het artikel geeft de details van de heapbewerkingen.
Een hoopdetails maken
create_heap
Zie hierboven!
ophopen
Zie hierboven
samenvoegen
Als de heaparrays,
89, 85, 87, 84, 82, 79, 73, 80, 81, , , 65, 69en
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71zijn samengevoegd, kan het resultaat zonder duplicaten zijn,
89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71Na wat zeven. Merk op dat in de eerste array 82 geen kinderen heeft. In de resulterende array bevindt deze zich op index 4; en de locaties op index 2(4)+1=9 en 2(4)+2=10 zijn vacant. Dit betekent dat het ook geen kinderen heeft in het nieuwe boomdiagram. De oorspronkelijke twee heaps mogen niet worden verwijderd, omdat hun informatie niet echt in de nieuwe heap staat (nieuwe array). Het basisalgoritme om hopen van hetzelfde type samen te voegen is als volgt:
- Voeg een array toe aan de onderkant van de andere array.
- Heapify elimineert duplicaten en zorgt ervoor dat knooppunten die geen kinderen in de oorspronkelijke heaps hadden, nog steeds geen kinderen in de nieuwe heap hebben.
versmelten
Het algoritme voor het samenvoegen van twee hopen van hetzelfde type (ofwel twee max- of twee min-) is als volgt:
- Vergelijk de twee hoofdknooppunten.
- Maak de minder extreme wortel en de rest van zijn boom (subboom), het tweede kind van de extreme wortel.
- Zeef het verdwaalde kind van de wortel van nu de extreme subboom, naar beneden in de extreme subboom.
De resulterende heap is nog steeds in overeenstemming met de heap-eigenschap, terwijl de originele heaps worden vernietigd (gewist). De originele hopen kunnen worden vernietigd omdat alle informatie die ze bezaten nog steeds in de nieuwe hoop zit.
Basis heapbewerkingen
find_max (find_min)
Dit betekent dat u de maximale waarde in de max-heap-array zoekt en een kopie retourneert, of de minimumwaarde in de min-heap-array zoekt en een kopie retourneert. Een heap-array voldoet per definitie al aan de eigenschap heap. Dus retourneer gewoon een kopie van het eerste element van de array.
invoegen
Dit betekent een nieuw element toevoegen aan de heap-array en de array opnieuw rangschikken zodat de heap-eigenschap van het diagram behouden blijft (voldaan). Het algoritme om dit voor beide soorten hopen te doen is als volgt:
- Neem aan dat een volledige binaire boom. Dit betekent dat de array indien nodig aan het einde gevuld moet worden met lege locaties. Het totale aantal knooppunten van een volledige heap is 1, of 3 of 7 of 15 of 31, enz.; blijf verdubbelen en 1 . toevoegen.
- Plaats het knooppunt op de meest geschikte lege locatie qua grootte, tegen het einde van de heap (tegen het einde van de heap-array). Als er geen lege locatie is, start dan een nieuwe rij vanaf linksonder.
- Zeef indien nodig, totdat aan de heap-eigenschap is voldaan.
extract_max (extract_min)
Zoek de maximale waarde in de max-heap-array, verwijder en retourneer deze; of zoek de minimumwaarde in de min-heap-array, verwijder en retourneer deze. Het algoritme voor extract_max (extract_min) is als volgt:
- Verwijder de root-node.
- Neem (verwijder) de meest rechtse knoop (laatste knoop in de array) en plaats deze in de root.
- Zeef waar nodig, totdat aan de heap-eigenschap is voldaan.
delete_max (delete_min)
Zoek het hoofdknooppunt van een max-heap, het eerste element van de max-heap-array, verwijder het zonder het noodzakelijkerwijs terug te geven; of zoek het hoofdknooppunt van een min-heap, het eerste element van de min-heap-array, verwijder het zonder het noodzakelijkerwijs terug te geven. Het algoritme om het hoofdknooppunt te verwijderen is als volgt:
- Verwijder de root-node.
- Neem (verwijder) de meest rechtse knoop (laatste knoop in de array) en plaats deze in de root.
- Zeef waar nodig, totdat aan de heap-eigenschap is voldaan.
vervangen
Lokaliseer het hoofdknooppunt van een van beide heaps, verwijder het en vervang het door de nieuwe. Het maakt niet uit of de oude root wordt geretourneerd. Zeef indien van toepassing, totdat aan de heap-eigenschap is voldaan.
Interne heapbewerkingen
verhoging_toets (verminder_toets)
Verhoog de waarde van een knooppunt voor een max-heap en herschikken zodat de heap-eigenschap behouden blijft, of verlaag de waarde van een willekeurig knooppunt voor een min-heap en herschikken zodat de heap-eigenschap behouden blijft. Zeef omhoog of omlaag zoals van toepassing, totdat aan de heap-eigenschap is voldaan.
verwijderen
Verwijder het gewenste knooppunt en herschik het, zodat de heap-eigenschap behouden blijft voor de max-heap of een min-heap. Het algoritme om een knoop te verwijderen is als volgt:
- Verwijder het knooppunt van belang.
- Neem (verwijder) het meest rechtse knooppunt (laatste knooppunt in de array) en plaats op de index van het verwijderde knooppunt. Als het verwijderde knooppunt zich in de laatste rij bevindt, is dit misschien niet nodig.
- Zeef omhoog of omlaag zoals van toepassing, totdat aan de heap-eigenschap is voldaan.
shift_up
Verplaats een knooppunt in een max-heap of min-heap zo lang als nodig is, herschikken om de heap-eigenschap te behouden - ziften.
terugschakelen
Verplaats een knooppunt naar beneden in een max-heap of min-heap zo lang als nodig is, herschikken om de heap-eigenschap te behouden - ziften.
Inspectie van een hoop
grootte
Zie hierboven!
is leeg
Zie hierboven!
Andere klassen van hopen
De in dit artikel beschreven hoop kan worden beschouwd als de belangrijkste (algemene) hoop. Er zijn andere soorten hopen he. De twee die u verder moet kennen, zijn echter de Binary Heap en de d-ary Heap.
Binaire hoop
De binaire heap is vergelijkbaar met deze hoofdheap, maar met meer beperkingen. In het bijzonder moet de binaire hoop een volledige boom zijn. Verwar niet tussen een volledige boom en een volledige boom.
d-ary Heap
Een binaire heap is een 2-ary heap. Een heap waarbij elke knoop 3 kinderen heeft, is een heap van 3 ary. Een heap waarbij elke knoop 4 kinderen heeft, is een heap van 4 tallen, enzovoort and. Een d-ary heap heeft andere beperkingen.
Conclusie
Een heap is een complete of bijna complete binaire boom die voldoet aan de heap-eigenschap. De eigenschap heap heeft 2 alternatieven: voor een max-heap moet een bovenliggende waarde gelijk of groter zijn dan de directe kinderen; voor een min-heap moet een ouder gelijk zijn aan of minder waard zijn dan de directe kinderen. Een hoop kan worden weergegeven als een boom of in een array. Wanneer weergegeven in een array, is het hoofdknooppunt het eerste knooppunt van de array; en als een knoop op index n staat, is het eerste kind in de array op index 2n+1 en het volgende kind op index 2n+2. Een heap heeft bepaalde bewerkingen die op de array worden uitgevoerd.
Chrys
