Het gebruik van gegevensstructuren is van vitaal belang op het gebied van computerprogrammering, vooral wanneer het gaat om het snel en efficiënt opslaan, beheren en organiseren van gegevens. Elke ontwikkelaar moet overwegen om gegevensstructuur grondig te begrijpen, omdat het zijn vaardigheden aanzienlijk kan verbeteren. Min en max heap implementatie zijn een belangrijk onderdeel van datastructuur en iedereen moet overwegen erover te leren.
Begrijpen wat Heap is
Heap, in zijn kern, is een geavanceerde boom-gebaseerde gegevensstructuur die programmeurs hoofdzakelijk gebruiken voor het implementeren en sorteren van wachtrijen. Heaps zijn binaire bomen en hier zijn hun primaire kenmerken:
- Het ingangsniveau in stapels is gevuld, met de bladknopen als uitzondering
- Alle nodes hebben maximaal 2 kinderen
- Elk knooppunt bevindt zich uiterst links, wat betekent dat elk kind zich links van zijn ouder bevindt
Heaps maken gebruik van binaire bomen om gaten in de array te vermijden. Binaire bomen zijn bomen waarin elk knooppunt twee kinderen heeft en elk knooppunt vol is, met als enige uitzondering de bladknooppunten, die leeg zijn. Heaps worden gecreëerd op hun eigenschap. De eigenschap vergelijkt in wezen de ouders met de sleutels van hun kinderknooppunten.
Vergeet niet dat heaps niet altijd gesorteerd zijn, en dat ze een sleutelvoorwaarde volgen waarbij het kleinste of het grootste element aanwezig is op de root node, afhankelijk van of het een Min of Max Heap is.
Voor- en nadelen van hopen
Voordelen
- Je kunt variabelen globaal benaderen
- Stapels zijn erg handig om de grootste en kleinste getallen te vinden
- Heaps zijn ongelooflijk flexibel en je kunt ze verwijderen of toewijzen in elke volgorde die je wilt
Nadelen
- Heaps vergen veel meer uitvoeringstijd in vergelijking met stacks
- De rekentijd die nodig is voor heaps is over het algemeen aan de hogere kant
- Geheugenbeheer kan een hele uitdaging zijn met heap geheugen. De reden hiervoor is dat heap over de hele wereld wordt gebruikt.
Heap Data Structuur Toepassingen
Heaps zijn ongelooflijk efficiënt als het gaat om het vinden van het max of min element in arrays. Ze zijn ook nuttig in selectie-algoritmen en statistieken. De tijd complexiteit om heap te gebruiken voor het verkrijgen van maximum of minimum waarde is O(1)O(1).
Programmeurs ontwerpen prioriteitswachtrijen op basis van de structuren van de heap. Het duurt ongeveer O(log(n))O(log(n)) voor het invoegen en verwijderen van alle elementen die zich in de prioriteitswachtrij bevinden met maximale efficiëntie.
Prioriteitswachtrijen (heap implemented) worden vaak aangetroffen in algoritmen zoals:
- Het heapsort algoritme
- Dijkstra’s algoritme
- Prim‘s algoritme
Essentiële hoop operaties
Hieronder staan de vitale operaties die men gebruikt bij het integreren van heap gegevensstructuren.
getMax(): Deze bewerking helpt om de maximale waarde in de heap terug te geven
size: De grootte operatie wordt gebruikt om de grootte van de heap terug te geven
extract: Extract helpt om de waarde van een item terug te geven, gevolgd door het te verwijderen van de heap
delete: Delete wordt gebruikt voor het verwijderen van items voor een heap
invoegen: Dit commando plaatst items op de hoop, en behoudt zijn eigendom.
heapify: Heapify herschikt de elementen van de hoop om de eigenschappen van de hoop te behouden.
Stappen om Max Heap te bouwen
Elk element in max heap heeft de neiging zich te gedragen volgens de max heap eigenschap, wat betekent dat de parent node’s key groter is dan de child node key’s elke keer. Volg deze stappen om max heap op de juiste manier op te bouwen:
- Vorm een nieuw knooppunt aan de oorspronkelijke wortel van de sprong
- Geef het een waarde
- Na het toewijzen van een waarde, vergelijkt u de waarden van de ouder- en kindnode
- Indien de ouder lager is dan een van de kinderen, verwissel dan de knopen
- Herhaal de stap totdat het grootste element de parent nodes van de root bereikt
U kunt deze stappen ook volgen wanneer u nieuwe elementen in een hoop opneemt. Onthoud dat, welke bewerking u ook uitvoert op een max. hoop, het van vitaal belang is de eigenschappen van de hoop te behouden.
Stappen voor het verwijderen/verwijderen van knooppunten in Max Heap
De onderstaande stappen zullen u helpen bij het effectief verwijderen of verwijderen van max heap nodes:
- Neem het laatste kind knooppunt en verplaats het naar het laatste niveau van de wortel
- Vergelijk de kinderen en ouder nodes
- Als de waarde van de ouder lager is dan de nodes van hun kind, is het het beste om ze te verwisselen, gevolgd door het herhalen van het proces totdat je de hoop bevredigt.
Zoals eerder vermeld, moet je vertrouwd raken met de verschillende datastructuren en begrijpen hoe je complexe coderingsgerelateerde vragen het best zelfverzekerd kan benaderen. Dit zal je ook helpen om een duidelijk idee te krijgen van de min en max heap implementatie, zodat je het zonder problemen kunt gebruiken.
Stappen om Min Heap te bouwen
Elementen aanwezig in min heap handelen over het algemeen in overeenstemming met de eigenschap van min heap, die sterk verschilt van hoe max heap werkt. Onthoud dat de key van de parent node altijd kleiner is dan de key van de child node. De volgende stappen kunnen je helpen om een min heap te maken:
- Vorm een gloednieuw kindknooppunt op het laagste niveau, dat is het einde van de hoop
- Neem de nieuwe sleutel op in het knooppunt
- Begin het kind naar boven te bewegen, zorg ervoor dat je voldoet aan de heap eigenschap door de root node te bereiken
Stappen om Rood Node in Min Heap te verwijderen of te verwijderen
- Ga verder door eenvoudig de root node te verwijderen
- Verplaats de sleutel van het laatste kind naar de wortel
- Voer een vergelijkende analyse uit tussen het knooppunt en zijn kinderen
- Als de waarde van de ouder hoger is dan die van de kindknopen, wissel ze dan om, en herhaal het proces tot je voldoet aan de heap eigenschap
Waarom hopen belangrijk zijn
Begrijpen hoe de min en max heap implementatie werkt is goed en wel, maar je moet ook de reden leren waarom heaps zo belangrijk zijn. Ten eerste hebben programmeurs gebruik gemaakt van heap in job scheduling besturingssystemen om te verzekeren dat werkgevers mensen kunnen oproepen volgens prioriteit. Je vindt heaps ook terug in verschillende heap sort algoritmes voor de implementatie van prioriteitswachtrijen. Dijkstra’s algoritme maakt ook gebruik van heap om korte paden te bepalen.