Mound - online puzzels

Een heap is een abstracte datastructuur in de informatica, niet te verwarren met een zogenaamd heapgeheugen. Op een heap kunnen data-elementen worden opgeslagen, maar daar ook weer uit verwijderd worden. Aan elk van de elementen is een sleutel toegewezen die de prioriteit van het element bepaalt. In veel gevallen kunnen de elementen zelf als sleutel gebruikt worden.

Een heap is een array-datastructuur die een binaire boom representeert. Een array A is een heap als deze voldoet aan de heapvoorwaarde: als B een kind van A is, dan sleutel(A) ≥ sleutel(B).

Bewerkingen

Element toevoegen

Er wordt gestart met een array A met grootte N. Het te plaatsen element wordt op de plaats N+1 gezet. Op dit moment is niet noodzakelijk voldaan aan de heapvoorwaarde (het element kan groter zijn dan zijn ouder).

Om terug aan de heapvoorwaarde te voldoen, worden volgende stappen herhaald totdat het element op zijn plaats staat, en dus kleiner is dan zijn ouder. Indien het toegevoegde element het grootste van de hele heap is, komt dit uiteindelijk zo in de wortel te staan.