Welke classificaties van heaps bestaan er in de context van datastructuren?

In de context van datastructuren wordt onder "heap" meestal een binaire heap (Binary Heap) verstaan, die de volgende classificaties heeft:

1. Volgens het type ordening:

   • Min-Heap: De waarde van elke knoop is kleiner dan of gelijk aan de waarden van zijn kindknopen. De wortel is het minimale element.
   • Max-Heap: De waarde van elke knoop is groter dan of gelijk aan de waarden van zijn kindknopen. De wortel is het maximale element.

2. Volgens de volledigheid van de boom:

   • Volledige binaire heap (Complete Binary Heap): Alle niveaus, behalve misschien de laatste, zijn volledig gevuld, en de knopen op het laatste niveau zijn zo ver mogelijk naar links geplaatst. Deze eigenschap is belangrijk omdat het de efficiënte opslag van de heap in een array mogelijk maakt.

   // Voorbeeldstructuur voor een heapknoop (ter demonstratie van het concept)
   public class HeapNode<T>
   {
       public T Value { get; set; }
       // Verwijzingen naar kindknopen zijn niet altijd expliciet in de arrayrepresentatie
       public HeapNode<T> Left { get; set; }
       public HeapNode<T> Right { get; set; }
   }
   

Hoewel er ook andere soorten heaps bestaan, zoals Fibonacci-heaps (voor geavanceerde algoritmen) of binomiale heaps, verwijst "heap" in de meeste gevallen naar een volledige binaire min- of max-heap vanwege hun brede toepassing in sorteeralgoritmen (bijvoorbeeld Heapsort) en prioriteitswachtrijen.