Heap

Een heap is in de informatica de tegenhanger van de datastructuur stack en bij veel programmeertalen het geheugengebied waar dynamisch gealloceerde opslag plaatsvindt.

De term is gangbaar geworden door de heapsort, maar is vanaf dat moment ook bekend als "garbage-collected storage" zoals die te vinden zijn in programmeertalen als Lisp en Java. In veel algoritmes wordt de heap echter niet gebruikt in die context.

Een heap is een matrix datastructuur om gegevens in op te slaan. Een heap kan gezien worden als een bijna complete boom van (binaire) gegevens. Elke positie (node) in de boom is een positie in de matrix die de data bevat. Elk niveau in de boom is in zijn geheel gevuld, met een eventuele uitzondering van het laagste niveau. Dit niveau moet altijd gezien worden vanaf de linkerkant van de boom.

Een matrix object dat gebruikt kan worden als een heap structuur heeft altijd twee attributen. Een attribuut wat de lengte van de boom aangeeft: $L e n g t e [A]$ . Dit is gelijk aan de grootte van de heap zelf. Het tweede attribuut is de grootte: $G r o o t t e [A]$ . Dit is gelijk aan het aantal elementen dat in de heap is opgeslagen.

Om het bovenstaande wat te verduidelijken, het kan zijn dat de lengte van een boom bijvoorbeeld 10 is, maar dat de grootte 8 is. We kunnen op dat moment dan ook zeggen dat $A [1.. l e n g t e [A]]$ geldige nummers kan bevatten, maar dat elk nummer vanaf $A [G r o o t t e [A]]$ waar $Grootte[A] \leq Lengte[A]$ geen onderdeel van de heap is. De wortel (root) van de heap is $A [1]$ .

Een heap hoeft niet in een boomstructuur opgeslagen te worden. De reden dat een matrix voldoet is dat de virtuele positie in de boom exact is af te leiden uit de positie in de matrix. Het element met index $n$ heeft als dochters de elementen met index $2 n$ en $2 n + 1$ (voor zover die indexen niet groter zijn dan de het totaal aantal elementen in de heap). De root heeft index 1.

min heap, alfabetisch gesorteerd

Er bestaan twee verschillende soorten heaps, de max-heap en de min-heap. Beide soorten hebben de regel dat elke node voldoet aan een heap eigenschap. De details hangen af van het soort heap. De max heap is de waarde waarin elke node anders dan de wortel (root) niet groter kan zijn dan de waarde die in de voorgaande node staat. In een max heap betekent dit dus dat de grootste waarde in de wortel (root) staat en dat elke onderliggende node waarden bevat die niet groter zijn dan wat er in de node zelf opgeslagen is.

Een max-heap kan samengevat worden in de regel:

$A[Ouder[i]] \geq A[i]$