Binaire heaps en binaire zoekbomen gebruikt in algoritmen - dummies

Een speciaal soort boomstructuur is de binary heap, die elk van de knooppuntelementen in een speciale volgorde plaatst. Door zoekbomen kunt u snel naar gegevens zoeken. Het verkrijgen van gegevensitems, ze in een gesorteerde volgorde in een boom plaatsen en vervolgens in die boom zoeken, is een van de snellere manieren om informatie te vinden.

In een binaire heap bevat het basisknooppunt altijd de kleinste waarde. Als je de takken bekijkt, zie je dat takken op het hoogste niveau altijd een kleinere waarde hebben dan takken en bladeren op een lager niveau. Het effect is om de boom in evenwicht te houden en in een voorspelbare volgorde, zodat het zoeken uiterst efficiënt wordt. De kosten zijn om de boom in balans te houden.

Van alle taken die applicaties uitvoeren, is zoeken meer tijdrovend en ook veeleisender. Hoewel het toevoegen van gegevens (en het later sorteren) enige tijd in beslag neemt, is het voordeel van het maken en onderhouden van een gegevensset dat deze wordt gebruikt om nuttig werk uit te voeren, wat betekent dat er naar belangrijke informatie wordt gezocht. Daarom kunt u soms langskomen met minder efficiënte CRUD-functionaliteit en zelfs een niet-optimale sorteerroutine, maar zoekopdrachten moeten zo efficiënt mogelijk verlopen. Het enige probleem is dat niemand elke taak met absolute efficiëntie uitvoert, dus u moet uw opties wegen op basis van wat u verwacht te doen als onderdeel van de zoekroutines.

Twee van de efficiëntere zoekmethoden zijn het gebruik van de binaire zoekboom (BST) en binaire heap. Beide zoektechnieken berusten op een boomachtige structuur om de sleutels te bevatten die worden gebruikt voor toegang tot gegevenselementen. De indeling van de twee methoden is echter anders, wat de reden is dat de ene voordelen heeft ten opzichte van de andere bij het uitvoeren van bepaalde taken. Deze figuur toont de rangschikking voor een BST.

De rangschikking van toetsen bij gebruik van een BST.

Merk op hoe de toetsen een volgorde volgen waarin kleinere getallen aan de linkerkant verschijnen en grotere getallen aan de rechterkant. Het wortelknooppunt bevat een waarde die zich in het midden van het bereik van toetsen bevindt, waardoor de BST een gemakkelijk te begrijpen gebalanceerde benadering krijgt voor het opslaan van de toetsen. Vergelijk deze opstelling met de binaire heap die hier wordt getoond.

De rangschikking van sleutels bij gebruik van een binaire heap.

Elk niveau bevat waarden die kleiner zijn dan het vorige niveau en de hoofdmap bevat de maximale sleutelwaarde voor de structuur. Bovendien verschijnen in dit geval de mindere waarden aan de linkerkant en de grotere aan de rechterkant (hoewel deze volgorde niet strikt wordt gehandhaafd). De figuur geeft eigenlijk een binaire maximumheap weer. U kunt ook een binaire min-heap maken waarin de hoofdmap de laagste sleutelwaarde bevat en elk niveau wordt gemaakt naar hogere waarden, waarbij de hoogste waarden worden weergegeven als onderdeel van de bladeren.

Zoals eerder opgemerkt heeft BST enkele voordelen ten opzichte van binaire heap wanneer deze wordt gebruikt om een ​​zoekopdracht uit te voeren. De volgende lijst bevat enkele van de hoogtepunten van deze voordelen:

• Zoeken naar een element vereist O (log n) tijd, in tegenstelling tot O (n) tijd voor een binaire heap.
• Het in volgorde afdrukken van de elementen vereist alleen O (log n) tijd, in tegenstelling tot O (n log n) tijd voor een binaire heap.
• Het vinden van de vloer en het plafond vereist O (log n) tijd.
• Lokaliseren van Kde kleinste / grootste element vereist O (log n) tijd wanneer de boom correct is geconfigureerd.

Of deze tijden belangrijk zijn, hangt af van uw toepassing. BST werkt het beste in situaties waarin u meer tijd besteedt aan zoeken en minder tijd aan het bouwen van de boom. Een binaire heap heeft de neiging het beste te werken in dynamische situaties waarin toetsen regelmatig veranderen. De binaire heap biedt ook voordelen, zoals beschreven in de volgende lijst:

• Het maken van de vereiste structuren vereist minder resources, omdat binary hopen afhankelijk zijn van arrays, waardoor ze ook cache vriendelijker worden.
• Het bouwen van een binaire heap vereist O (n) tijd, in tegenstelling tot BST, waarvoor O (n log n) tijd vereist is.
• Pointers gebruiken om de boom te implementeren is niet nodig.
• Vertrouwen op binaire heapvariaties (bijvoorbeeld de Fibonacci Heap) biedt voordelen zoals het verhogen en verlagen van kerntijden van O (1) tijd.