Heap

Een heap is een gegevensstructuur die bestaat uit "knopen" met waarden. Een typische heap heeft bovenaan een hoofdknoop, die direct daaronder twee of meer onderliggende knopen kan hebben. Elke knoop kan twee of meer onderliggende knopen hebben, waardoor de heap met elke onderliggende knoop breder wordt. Wanneer een heap visueel wordt weergegeven, ziet deze eruit als een omgekeerde boom en heeft de algemene vorm die van een hoop.

Hoewel elke knoop in een heap twee of meer onderliggende knopen kan hebben (ook wel "kinderen" genoemd), beperken de meeste heaps elke knoop tot twee kinderen. Dit soort heaps worden ook binaire heaps genoemd en kunnen worden gebruikt om gesorteerde gegevens op te slaan. Een "binaire max-heap" slaat bijvoorbeeld de hoogste waarde op in de hoofdknoop. De op één na hoogste en de op twee na hoogste waarde worden opgeslagen in de onderliggende knopen van de hoofdknoop. In de hele boom heeft elke knoop een grotere waarde dan elk van zijn onderliggende knopen. Een "binaire min-heap" werkt omgekeerd: de hoofdknoop bevat de laagste waarde en elke knoop heeft een lagere waarde dan zijn onderliggende knopen.

In de informatica worden heaps vaak weergegeven als eenvoudige diagrammen. Het daadwerkelijk opslaan van gegevens in een heap is echter complexer. Om een heap te maken, moeten programmeurs afzonderlijke algoritmen schrijven voor het invoegen en verwijderen van gegevens. De waarden die in een heap worden ingevoegd, worden meestal opgeslagen in een array, waarnaar kan worden verwezen door een programma. Omdat de gegevens in een heap al zijn gesorteerd, biedt deze een efficiënte manier om naar specifieke waarden te zoeken.

NOTE: "De heap" is ook een programmeerterm die kan worden gebruikt om dynamisch toegewezen geheugen te beschrijven. Dit geheugenblok kan worden gebruikt door actieve toepassingen. Omdat geheugen in de heap dynamisch wordt toegewezen, kan de heap groter of kleiner worden afhankelijk van hoeveel geheugen wordt gebruikt.