Quali sono le classificazioni degli heap nel contesto delle strutture dati?

Nel contesto delle strutture dati, per "heap" (monticolo) si intende generalmente un heap binario (Binary Heap), che presenta le seguenti classificazioni:

1. Per tipo di ordinamento:

   • Monticolo minimo (Min-Heap): Il valore di ogni nodo è minore o uguale ai valori dei suoi nodi figli. La radice è l’elemento minimo.
   • Monticolo massimo (Max-Heap): Il valore di ogni nodo è maggiore o uguale ai valori dei suoi nodi figli. La radice è l’elemento massimo.

2. Per completezza dell’albero:

   • Monticolo binario completo (Complete Binary Heap): Tutti i livelli, tranne forse l’ultimo, sono completamente pieni, e i nodi dell’ultimo livello sono disposti il più a sinistra possibile. Questa proprietà è importante perché permette di memorizzare efficacemente il monticolo in un array.

   // Esempio di struttura per un nodo del monticolo (per dimostrare il concetto)
   public class HeapNode<T>
   {
       public T Value { get; set; }
       // I riferimenti ai nodi figli non sono sempre espliciti nella rappresentazione in array
       public HeapNode<T> Left { get; set; }
       public HeapNode<T> Right { get; set; }
   }
   

Sebbene esistano altri tipi di monticoli, come il monticolo di Fibonacci (per algoritmi avanzati) o il monticolo binomiale, nella maggior parte dei casi, "monticolo" si riferisce specificamente a un monticolo binario completo di minimo o massimo a causa del loro ampio impiego negli algoritmi di ordinamento (ad esempio Heapsort) e nelle code di priorità.