Jaké jsou klasifikace hald v kontextu datových struktur?

V kontextu datových struktur se pod pojmem "halda" (Heap) obvykle rozumí binární halda (Binary Heap), která má následující klasifikace:

1. Podle typu řazení:

   • Min-heap (Min-halda): Hodnota každého uzlu je menší nebo rovna hodnotám jeho potomků. Kořen je nejmenším prvkem.
   • Max-heap (Max-halda): Hodnota každého uzlu je větší nebo rovna hodnotám jeho potomků. Kořen je největším prvkem.

2. Podle úplnosti stromu:

   • Kompletní binární halda (Complete Binary Heap): Všechny úrovně, kromě možná poslední, jsou zcela zaplněny a uzly na poslední úrovni jsou umístěny co nejvíce vlevo. Tato vlastnost umožňuje efektivní ukládání haldy v poli.

   // Příklad struktury pro uzel haldy (pro demonstraci konceptu)
   public class HeapNode<T>
   {
       public T Value { get; set; }
       // Odkazy na potomky nejsou vždy explicitní v polem reprezentaci
       public HeapNode<T> Left { get; set; }
       public HeapNode<T> Right { get; set; }
   }
   

Ačkoliv existují i jiné typy hald, například Fibonacci halda (pro pokročilé algoritmy) nebo binomická halda, ve většině případů se "halda" odkazuje na úplnou binární min- nebo max-hald, kvůli jejich širokému využití v třídicích algoritmech (například Heapsort) a prioritních frontách.