Ce clasificări ale heap-urilor există în contextul structurilor de date?

În contextul structurilor de date, sub termenul de "heap" (heap) se înțelege de obicei un heap binar (Binary Heap), care are următoarele clasificări:

1. După tipul de ordonare:

   • Heap minim (Min-Heap): Valoarea fiecărui nod este mai mică sau egală cu valorile nodurilor sale copil. Rădăcina este elementul minim.
   • Heap maxim (Max-Heap): Valoarea fiecărui nod este mai mare sau egală cu valorile nodurilor sale copil. Rădăcina este elementul maxim.

2. După completitudinea arborelui:

   • Heap binar complet (Complete Binary Heap): Toate nivelurile, cu excepția posibil ultimele, sunt complet umplute, iar nodurile de pe ultimul nivel sunt plasate cât mai la stânga posibil. Această proprietate este importantă deoarece permite stocarea eficientă a heap-ului într-un array.

   // Exemplu de structură pentru un nod de heap (pentru demonstrarea conceptului)
   public class HeapNode<T>
   {
       public T Value { get; set; }
       // Referințele către nodurile copil nu sunt întotdeauna explicite în reprezentarea în array
       public HeapNode<T> Left { get; set; }
       public HeapNode<T> Right { get; set; }
   }
   

Deși există și alte tipuri de heap-uri, cum ar fi heap-ul Fibonacci (pentru algoritmi avansați) sau heap-ul binomial, în cele mai multe cazuri, "heap" se referă în mod specific la un heap binar complet de minim sau maxim, datorită utilizării lor extinse în algoritmi de sortare (de exemplu, Heapsort) și cozi de prioritate.