what is heap data structure java
Deze tutorial legt uit wat Java Heap Data Structure en gerelateerde concepten is, zoals Min Heap, Max Heap, Heap Sort, Stack vs Heap met voorbeelden:
Een heap is een speciale datastructuur in Java. Een heap is een op een boom gebaseerde datastructuur en kan worden geclassificeerd als een complete binaire boom. Alle knooppunten van de hoop zijn in een specifieke volgorde gerangschikt.
Bezoek hier om de Java-trainingsserie voor iedereen te zien
Wat je leert:
Heap-gegevensstructuur in Java
In de heap-datastructuur wordt het hoofdknooppunt vergeleken met zijn kinderen en gerangschikt volgens de volgorde. Dus als a een root-node is en b het kind is, dan is de eigenschap, key (a)> = key (b) genereert een maximale heap.
De bovenstaande relatie tussen de root en de onderliggende node wordt 'Heap Property' genoemd.
Afhankelijk van de volgorde van bovenliggende en onderliggende knooppunten, bestaat de heap over het algemeen uit twee typen:
# 1) Max-Heap In een Max-Heap is de root-knooppuntsleutel de grootste van alle sleutels in de heap. Er moet voor worden gezorgd dat dezelfde eigenschap recursief geldt voor alle substructuren in de heap.
Het onderstaande diagram toont een voorbeeld van een maximale heap. Merk op dat het hoofdknooppunt groter is dan zijn kinderen.
# 2) Min-Heap In het geval van een Min-Heap is de root-knooppuntsleutel de kleinste of het minimum van alle andere sleutels die in de heap aanwezig zijn. Net als in Max heap, zou deze eigenschap recursief true moeten zijn in alle andere substructuren in de heap.
Een voorbeeld, van een Min-heap-boom, wordt hieronder weergegeven. Zoals we kunnen zien, is de root-sleutel de kleinste van alle andere sleutels in de heap.
Een heap-datastructuur kan worden gebruikt in de volgende gebieden:
- Heaps worden meestal gebruikt om prioriteitswachtrijen te implementeren.
- Vooral min-heap kan worden gebruikt om de kortste paden tussen de hoekpunten in een grafiek te bepalen.
Zoals eerder vermeld, is de heap-gegevensstructuur een complete binaire boom die voldoet aan de heap-eigenschap voor root en de kinderen. Deze heap wordt ook wel een binaire hoop
Binaire hoop
Een binaire heap voldoet aan de onderstaande eigenschappen:
- Een binaire heap is een complete binaire boom. In een complete binaire boom zijn alle niveaus behalve het laatste niveau volledig gevuld. Op het laatste niveau zijn de toetsen zo ver mogelijk naar links.
- Het voldoet aan de heap-eigenschap. De binaire heap kan max of min-heap zijn, afhankelijk van de heap-eigenschap die eraan voldoet.
Een binaire heap wordt normaal gesproken weergegeven als een array. Omdat het een complete binaire boom is, kan het gemakkelijk worden weergegeven als een array. Dus in een array-weergave van een binaire heap, zal het root-element A [0] zijn, waarbij A de array is die wordt gebruikt om de binaire heap weer te geven.
Dus in het algemeen voor elke ithknooppunt in de binaire heap-array-weergave, A [i], kunnen we de indices van andere knooppunten weergeven, zoals hieronder wordt weergegeven.
A [(i-1) / 2] | Vertegenwoordigt het bovenliggende knooppunt |
---|---|
Toegang is sneller. | Langzamer dan de stapel. |
A [(2 * i) +1] | Vertegenwoordigt het linker onderliggende knooppunt |
A [(2 * i) +2] | Vertegenwoordigt het juiste onderliggende knooppunt |
Beschouw de volgende binaire heap:
De matrixweergave van de bovenstaande min binaire heap is als volgt:
Zoals hierboven getoond, wordt de heap doorlopen volgens de niveau volgorde d.w.z. de elementen worden op elk niveau van links naar rechts doorlopen. Wanneer de elementen op het ene niveau uitgeput zijn, gaan we verder naar het volgende niveau.
Vervolgens zullen we de binaire heap in Java implementeren.
Het onderstaande programma demonstreert de binaire heap in Java.
Uitgang:
nHeap = 7 4 6 1 3 2 5
Min Heap in Java
Een min-heap in Java is een complete binaire boom. In min-heap is het hoofdknooppunt kleiner dan alle andere knooppunten in de heap. In het algemeen is de sleutelwaarde van elk intern knooppunt kleiner dan of gelijk aan de onderliggende knooppunten.
Wat betreft de array-weergave van de min-heap: als een knooppunt is opgeslagen op positie ‘i’, wordt het linker onderliggende knooppunt opgeslagen op positie 2i + 1 en vervolgens bevindt het rechter onderliggende knooppunt zich op positie 2i + 2. De positie (i-1) / 2 geeft zijn bovenliggende knoop terug.
Hieronder staan de verschillende bewerkingen die worden ondersteund door min-heap.
# 1) Invoegen (): In eerste instantie wordt aan het einde van de boom een nieuwe sleutel toegevoegd. Als de sleutel groter is dan het bovenliggende knooppunt, blijft de heap-eigenschap behouden. Anders moeten we de sleutel naar boven verplaatsen om aan de heap-eigenschap te voldoen. Invoegbewerking in min heap duurt O (log n) tijd.
# 2) extractMin (): Met deze bewerking wordt het minimumelement uit de heap verwijderd. Merk op dat de heap-eigenschap moet worden gehandhaafd nadat het root-element (min-element) uit de heap is verwijderd. Deze hele operatie duurt O (Logn).
# 3) getMin (): getMin () retourneert de root van de heap die ook het minimumelement is. Deze bewerking wordt uitgevoerd in O (1) tijd.
Hieronder is een voorbeeldboom voor een Min-heap gegeven.
Het bovenstaande diagram toont een min-heap-boom. We zien dat de wortel van de boom het minimale element in de boom is. Omdat de wortel zich op locatie 0 bevindt, wordt het linkerkind op 2 * 0 + 1 = 1 geplaatst en het rechterkind op 2 * 0 + 2 = 2.
Min Heap-algoritme
Hieronder wordt het algoritme weergegeven voor het bouwen van een min-heap.
Min Heap-implementatie in Java
We kunnen de min-heap implementeren met behulp van array- of prioriteitswachtrijen. Het implementeren van min-heap met behulp van prioriteitswachtrijen is de standaardimplementatie, aangezien een prioriteitswachtrij wordt geïmplementeerd als min-heap.
Het volgende Java-programma implementeert de min-heap met behulp van arrays. Hier gebruiken we matrixrepresentatie voor heap en passen vervolgens de heapify-functie toe om de heap-eigenschap van elk element dat aan de heap wordt toegevoegd, te behouden. Ten slotte laten we de heap zien.
Uitgang:
Max. Hoop in Java
Een max heap is ook een complete binaire boom. In een maximale heap is het hoofdknooppunt groter dan of gelijk aan de onderliggende knooppunten. Over het algemeen is de waarde van elk intern knooppunt in een max-heap groter dan of gelijk aan de onderliggende knooppunten.
Terwijl max heap wordt toegewezen aan een array, wordt, als een knooppunt is opgeslagen op positie ‘i’, het linkerkind opgeslagen op 2i +1 en het rechterkind opgeslagen op 2i + 2.
Typische Max-heap ziet er uit zoals hieronder weergegeven:
In het bovenstaande diagram zien we dat het hoofdknooppunt de grootste heap is en dat de onderliggende knooppunten waarden hebben die kleiner zijn dan het hoofdknooppunt.
Net als bij min-heap, kan de max heap ook worden weergegeven als een array.
Dus als A een array is die Max heap vertegenwoordigt, dan is A [0] het hoofdknooppunt. Evenzo, als A [i] een knooppunt is in de max heap, dan zijn de volgende de andere aangrenzende knooppunten die kunnen worden weergegeven met behulp van een array.
- A [(i-1) / 2] vertegenwoordigt het bovenliggende knooppunt van A [i].
- A [(2i +1)] vertegenwoordigt het linker kindknooppunt van A [i].
- A [2i + 2] geeft het rechter kindknooppunt van A [i] terug.
De bewerkingen die kunnen worden uitgevoerd op de Max Heap worden hieronder gegeven.
# 1) Invoegen: Invoegbewerking voegt een nieuwe waarde in de max heap-structuur in. Het wordt aan het einde van de boom ingevoegd. Als de nieuwe sleutel (waarde) kleiner is dan het bovenliggende knooppunt, blijft de heap-eigenschap behouden. Anders moet de boom worden gestapeld om de eigenschap heap te behouden.
software om dvd naar pc te rippen
De tijdcomplexiteit van de invoegbewerking is O (log n).
# 2) ExtractMax: De bewerking ExtractMax verwijdert het maximum element (root) uit de max heap. De bewerking heap ook de max heap om de heap-eigenschap te behouden. De tijdcomplexiteit van deze bewerking is O (log n).
# 3) getMax: getMax-bewerking retourneert het hoofdknooppunt van de max-heap met de tijdcomplexiteit van O (1).
Het onderstaande Java-programma implementeert de max heap. We maken hier gebruik van ArrayList om de max heap-elementen weer te geven.
Uitgang:
Min. Hoop voor prioriteitswachtrij in Java
De datastructuur van de prioriteitswachtrij in Java kan direct worden gebruikt om de min-heap weer te geven. Standaard implementeert de prioriteitswachtrij min-heap.
Het onderstaande programma demonstreert de min-heap in Java met behulp van de Priority Queue.
Uitgang:
Prioriteitswachtrij Max. Hoop in Java
Om de maximale heap in Java weer te geven met behulp van de prioriteitswachtrij, moeten we Collections.reverseOrder gebruiken om de min-heap om te keren. De prioriteitswachtrij vertegenwoordigt rechtstreeks een min-heap in Java.
We hebben de Max Heap geïmplementeerd met behulp van een prioriteitswachtrij in het onderstaande programma.
Uitgang:
Heap Sorteren in Java
Heap-sortering is een vergelijkende sorteertechniek vergelijkbaar met selectiesortering, waarbij we voor elke iteratie een maximumelement in de array selecteren. Heap-sortering maakt gebruik van de Heap-datastructuur en sorteert de elementen door min of max heap te maken uit de array-elementen die moeten worden gesorteerd.
We hebben al besproken dat in min en max heap de root node respectievelijk het minimum en maximum element van de array bevat. Bij heap-sortering wordt het hoofdelement van de heap (min of max) verwijderd en naar de gesorteerde array verplaatst. De resterende heap wordt vervolgens als een stapel aangemaakt om de heap-eigenschap te behouden.
We moeten dus twee stappen recursief uitvoeren om de gegeven array te sorteren met behulp van heap sort.
- Bouw een hoop op uit de gegeven array.
- Verwijder het root-element herhaaldelijk uit de heap en verplaats het naar de gesorteerde array. Verhoog de resterende hoop.
Tijdscomplexiteit van Heap-sortering is in alle gevallen O (n log n). De ruimtecomplexiteit is O (1).
Heap Sort-algoritme in Java
Hieronder staan de heap-sorteeralgoritmen om de gegeven array in oplopende en aflopende volgorde te sorteren.
# 1) Heap Sort-algoritme om in oplopende volgorde te sorteren:
- Maak een maximale heap voor de opgegeven array die moet worden gesorteerd.
- Verwijder de root (maximale waarde in de invoerarray) en verplaats deze naar de gesorteerde array. Plaats het laatste element in de array bij de wortel.
- Heapify de nieuwe root van de heap.
- Herhaal stap 1 en 2 totdat de hele array is gesorteerd.
# 2) Heap Sort-algoritme om in aflopende volgorde te sorteren:
- Construeer een min Heap voor de gegeven array.
- Verwijder de root (minimumwaarde in de array) en verwissel deze met het laatste element in de array.
- Heapify de nieuwe root van de heap.
- Herhaal stap 1 en 2 totdat de hele array is gesorteerd.
Heap Sort-implementatie in Java
Het onderstaande Java-programma gebruikt heap sort om een array in oplopende volgorde te sorteren. Hiervoor construeren we eerst een max heap en vervolgens recursief het root-element omwisselen en heapifyen zoals gespecificeerd in het bovenstaande algoritme.
Uitgang:
De totale tijdcomplexiteit van de heap-sorteertechniek is O (nlogn). De tijdcomplexiteit van de heapify-techniek is O (logn). Terwijl de tijdcomplexiteit van het bouwen van de hoop O (n) is.
Stack versus Heap in Java
Laten we nu enkele verschillen tussen een Stack-gegevensstructuur en een heap in tabelvorm weergeven.
Stapel | Hoop |
---|---|
Een stapel is een lineaire gegevensstructuur. | Een heap is een hiërarchische gegevensstructuur. |
Volgt de bestelling van LIFO (Last In, First Out). | Traversal is op niveau. |
Meestal gebruikt voor statische geheugentoewijzing. | Gebruikt voor dynamische geheugentoewijzing. |
Geheugen wordt aaneengesloten toegewezen. | Geheugen wordt op willekeurige locaties toegewezen. |
De stapelgrootte is beperkt volgens het besturingssysteem. | Geen limiet op de heapgrootte afgedwongen door het besturingssysteem. |
Stack heeft alleen toegang tot lokale variabelen. | Heap heeft globale variabelen toegewezen gekregen. |
De toewijzing / de toewijzing van geheugen is automatisch. | Toewijzing / ongedaan maken van toewijzing moet handmatig worden gedaan door de programmeur. |
De stapel kan worden geïmplementeerd met behulp van Arrays, Linked List, ArrayList, enz. Of andere lineaire gegevensstructuren. | Heap wordt geïmplementeerd met behulp van arrays of bomen. |
Indien minder onderhoudskosten. | Kostbaarder in onderhoud. |
Kan leiden tot een tekort aan geheugen omdat het geheugen beperkt is. | Geen gebrek aan geheugen, maar kan last hebben van geheugenfragmentatie. |
Veel Gestelde Vragen
V # 1) Is stack sneller dan Heap?
Antwoord: Een stapel is sneller dan een hoop, aangezien de toegang lineair is in de stapel in vergelijking met de stapel.
V # 2) Waar wordt een Heap voor gebruikt?
Antwoord: Heap wordt meestal gebruikt in algoritmen die het minimum of kortste pad tussen twee punten vinden, zoals het algoritme van Dijkstra, om te sorteren met heap-sortering, voor prioriteitswachtrij-implementaties (min-heap), enz.
V # 3) Wat is een hoop? Welke soorten zijn er?
Antwoord: Een heap is een hiërarchische, boomgebaseerde gegevensstructuur. Een hoop is een complete binaire boom. Heaps zijn van twee typen, namelijk Max heap waarin het hoofdknooppunt het grootste is van alle knooppunten; Min. Heap waarin het hoofdknooppunt het kleinste of minimum is van alle sleutels.
V # 4) Wat zijn de voordelen van Heap ten opzichte van een stapel?
Antwoord: Het grote voordeel van de heap over stack is in heap, het geheugen wordt dynamisch toegewezen en daarom is er geen limiet aan hoeveel geheugen kan worden gebruikt. Ten tweede kunnen alleen lokale variabelen op de stapel worden toegewezen, terwijl we ook globale variabelen op de heap kunnen toewijzen.
V # 5) Kan Heap duplicaten hebben?
Antwoord: Ja, er zijn geen beperkingen voor het hebben van knooppunten met dubbele sleutels in de heap, aangezien de heap een complete binaire boom is en niet voldoet aan de eigenschappen van de binaire zoekboom.
Gevolgtrekking
In deze zelfstudie hebben we de soorten heap- en heap-sortering besproken met behulp van heap-typen. We hebben ook de gedetailleerde implementatie van zijn typen in Java gezien.
Bekijk hier de perfecte Java-trainingsgids.
Aanbevolen literatuur
- Java Graph Tutorial - Hoe Graph Data Structure te implementeren
- Inleiding tot gegevensstructuren in C ++
- Heap Sorteren in C ++ met voorbeelden
- AVL Tree and Heap-gegevensstructuur in C ++
- Binaire boomgegevensstructuur in C ++
- Wachtrijgegevensstructuur in C ++ met illustratie
- Circulaire gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Java Basics: Java Syntax, Java Class en Core Java Concepts