Wat doet heap push en hoe voegt het een element toe aan de heap?

Heap push — is een operatie waarbij een nieuw element wordt toegevoegd aan de datastructuur 'heap', die de eigenschappen van de heap (bijvoorbeeld minimaal of maximaal) behoudt.

Hoe de toevoeging plaatsvindt:

1. Het nieuwe element wordt aan het einde van de array geplaatst die de heap vertegenwoordigt.
2. Vervolgens wordt de operatie "sift-up" (sift-up of bubble-up) uitgevoerd: het element wordt vergeleken met zijn ouder, en als de heap-eigenschap wordt geschonden (bijvoorbeeld, in een min-heap, als het element kleiner is dan de ouder), worden de elementen van plaats verwisseld.
3. Dit proces wordt herhaald totdat het element op de juiste positie staat, waardoor de heap-eigenschappen worden hersteld.

Op deze manier zorgt heap push voor het toevoegen van een element met behoud van de ordening van de heap, wat het efficiënt maken van het extraheren van het minimale of maximale element mogelijk maakt.

Voorbeeld in Python met de module heapq:

import heapq

heap = [1, 3, 5, 7]
heapq.heapify(heap)  # Zet de lijst om in een heap

heapq.heappush(heap, 2)  # Voegt het element 2 toe
print(heap)  # Heap met behoud van de volgorde

Als resultaat wordt het element 2 toegevoegd en "sift-up" om de eigenschappen van de min-heap te behouden.