Какая есть классификация у структуры данных «куча» (heap)?

Куча (heap) как структура данных классифицируется по свойству упорядочивания элементов относительно родителя. Основные типы:

1. Максимальная куча (Max Heap):

   • Ключ каждого узла больше или равен ключам его дочерних узлов.
   • Корень содержит максимальный элемент.
   • Используется для реализации очереди с приоритетом, где нужен быстрый доступ к наибольшему элементу.

     // Свойство Max Heap: A[parent(i)] >= A[i]
     int[] maxHeapExample = { 100, 40, 50, 10, 15, 30, 20 };
     //         100
     //        /   
     //      40     50
     //     /     /  
     //    10  15 30  20

2. Минимальная куча (Min Heap):

   • Ключ каждого узла меньше или равен ключам его дочерних узлов.
   • Корень содержит минимальный элемент.
   • Применяется в алгоритмах, таких как алгоритм Дейкстры или для сортировки HeapSort в порядке возрастания.

     // Свойство Min Heap: A[parent(i)] <= A[i]
     int[] minHeapExample = { 5, 10, 20, 25, 15, 30 };
     //          5
     //        /   
     //      10     20
     //     /     /
     //    25  15 30

Дополнительные классификации по реализации:

• Бинарная куча: Наиболее распространенная реализация на основе полного бинарного дерева, эффективно хранимая в массиве.
• d-арная куча: Узлы имеют до d дочерних элементов, что может уменьшить высоту дерева и ускорить некоторые операции за счет увеличения сравнений на одном уровне.
• Фибоначчиева куча: Более сложная структура с амортизированно лучшим временем для операции уменьшения ключа (O(1)), используется в advanced алгоритмах.

Практическое применение в .NET: Класс PriorityQueue<TElement, TPriority> (появился в .NET 6) внутренне использует минимальную кучу (min-heap) для эффективного извлечения элемента с наивысшим приоритетом.