Jakie są klasyfikacje kopców w kontekście struktur danych?

W kontekście struktur danych, pod pojęciem "kopiec" (Heap) najczęściej rozumie się kopiec binarny (Binary Heap), który posiada następujące klasyfikacje:

1. Według typu uporządkowania:

   • Kopiec minimalny (Min-Heap): Wartość każdego węzła jest mniejsza lub równa wartościom jego węzłów potomnych. Korzeń jest elementem minimalnym.
   • Kopiec maksymalny (Max-Heap): Wartość każdego węzła jest większa lub równa wartościom jego węzłów potomnych. Korzeń jest elementem maksymalnym.

2. Według pełności drzewa:

   • Pełny kopiec binarny (Complete Binary Heap): Wszystkie poziomy, z wyjątkiem być może ostatniego, są w pełni wypełnione, a węzły na ostatnim poziomie są ułożone jak najbliżej lewej strony, jak to możliwe. Ta własność jest ważna, ponieważ umożliwia efektywne przechowywanie kopca w tablicy.

   // Przykład struktury dla węzła kopca (do demonstracji koncepcji)
   public class HeapNode<T>
   {
       public T Value { get; set; }
       // Odwołania do węzłów potomnych nie zawsze są jawne w reprezentacji tablicowej
       public HeapNode<T> Left { get; set; }
       public HeapNode<T> Right { get; set; }
   }
   

Chociaż istnieją inne rodzaje kopców, takie jak kopiec Fibonacciego (dla zaawansowanych algorytmów) czy kopiec binominalny, w większości przypadków "kopiec" odnosi się do pełnego kopca binarnego minimalnego lub maksymalnego ze względu na ich szerokie zastosowanie w algorytmach sortowania (np. Heapsort) i kolejach priorytetowych.