Какие существуют классификации кучи в контексте структур данных?

В контексте структур данных под "кучей" (Heap) чаще всего понимается двоичная куча (Binary Heap), обладающая следующими классификациями:

1. По типу упорядоченности:

   • Куча минимума (Min-Heap): Значение каждого узла меньше или равно значениям его дочерних узлов. Корень является минимальным элементом.
   • Куча максимума (Max-Heap): Значение каждого узла больше или равно значениям его дочерних узлов. Корень является максимальным элементом.

2. По полноте дерева:

   • Полная двоичная куча (Complete Binary Heap): Все уровни, кроме, возможно, последнего, полностью заполнены, а узлы на последнем уровне расположены как можно левее. Это важное свойство, позволяющее эффективно хранить кучу в массиве.

   // Пример структуры для элемента кучи (для демонстрации концепции)
   public class HeapNode<T>
   {
       public T Value { get; set; }
       // Ссылки на дочерние элементы не всегда явные в массивном представлении
       public HeapNode<T> Left { get; set; }
       public HeapNode<T> Right { get; set; }
   }
   

Хотя существуют и другие виды куч, такие как Фибоначчиева куча (用于高级算法) или Биномиальная куча, в большинстве случаев под "кучей" имеют в виду именно полную двоичную кучу минимума или максимума из-за их широкого применения в алгоритмах сортировки (например, Heapsort) и очередях с приоритетом.