Свойство кучи

Свойство кучи (англ. heap property) — это фундаментальное свойство бинарной кучи (двоичной кучи), структуры данных, представляющей собой полное бинарное дерево, в котором для каждого узла выполняется определённое отношение порядка между значением этого узла и значениями его дочерних узлов. Свойство кучи является ключевым для организации данных в куче и обеспечивает эффективное выполнение операций вставки, удаления и поиска минимального или максимального элемента.

Определение и основная идея

Свойство кучи определяет, каким образом значения узлов в дереве соотносятся друг с другом. Существуют два основных типа свойства кучи: свойство max-кучи (максимальной кучи) и свойство min-кучи (минимальной кучи).

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

В обоих случаях свойство кучи является локальным — оно проверяется для каждой пары «родитель — дочерний узел». Из этого следует, что свойство кучи не гарантирует какой-либо глобальной упорядоченности, кроме того, что корень является экстремумом (максимумом или минимумом). Например, в max-куче левый дочерний узел может быть больше правого, и это не нарушает свойства кучи, так как важно только отношение с родителем.

История и происхождение

Понятие бинарной кучи и её свойства были введены в 1964 году английским учёным Дж. У. Дж. Уильямсом (J. W. J. Williams) в контексте алгоритма пирамидальной сортировки (heapsort). Уильямс предложил использовать бинарное дерево, удовлетворяющее свойству кучи, для эффективного извлечения максимального элемента. Позднее, в 1964 году, Роберт Флойд (Robert W. Floyd) усовершенствовал алгоритм, предложив метод построения кучи за линейное время (процедура heapify). С тех пор свойство кучи стало основой для многих алгоритмов и структур данных, включая очереди с приоритетом (priority queues) и алгоритм Дейкстры для поиска кратчайших путей в графах.

Математическая формулировка

Пусть A — массив, представляющий бинарную кучу, где для каждого индекса i (начиная с 1) левый дочерний узел имеет индекс 2i, а правый — 2i+1. Тогда свойство кучи можно записать следующим образом:

• Для max-кучи: A[parent(i)] >= A[i] для всех i > 1, где parent(i) = floor(i/2).
• Для min-кучи: A[parent(i)] <= A[i] для всех i > 1.

Это условие должно выполняться для каждого узла, кроме корня.

Типы куч и их свойства

Бинарная куча (двоичная куча)

Наиболее распространённая реализация — бинарная куча, которая представляет собой полное бинарное дерево. Она может быть как max-кучей, так и min-кучей. Основные операции:

• Вставка: новый элемент добавляется в конец массива (в последний уровень дерева), затем «всплывает» (процедура sift-up или heapify-up) до тех пор, пока не будет восстановлено свойство кучи. Время выполнения — O(log n).
• Удаление корня: корень заменяется последним элементом массива, который затем «опускается» (процедура sift-down или heapify-down) до восстановления свойства кучи. Время выполнения — O(log n).
• Построение кучи из массива: выполняется за O(n) с помощью процедуры heapify, применённой к каждому внутреннему узлу, начиная с последнего.

D-куча (d-ary heap)

Обобщение бинарной кучи, где каждый узел имеет до d дочерних узлов. Свойство кучи формулируется аналогично: для max-кучи значение родителя не меньше значений всех его дочерних узлов. D-кучи используются для оптимизации операций вставки и удаления в зависимости от соотношения частоты этих операций. Например, при большом количестве вставок выгодно иметь большее d, так как операция вставки (всплытие) требует меньше сравнений.

Фибоначчиева куча

Более сложная структура данных, которая также удовлетворяет свойству кучи, но не является полным бинарным деревом. В фибоначчиевой куче допускаются деревья произвольной формы, но свойство кучи сохраняется для каждого узла. Эта структура позволяет выполнять операции вставки и уменьшения ключа за амортизированное O(1), а удаление минимума — за O(log n). Фибоначчиевы кучи применяются в алгоритмах, где требуется много операций уменьшения ключа, например, в алгоритме Дейкстры.

Биномиальная куча

Состоит из набора биномиальных деревьев, каждое из которых удовлетворяет свойству кучи. Биномиальные деревья рекурсивно определены: биномиальное дерево ранга k состоит из корня и k дочерних биномиальных деревьев рангов от 0 до k-1. Свойство кучи выполняется для каждого дерева. Биномиальные кучи поддерживают операции слияния (union) за O(log n), что делает их полезными для реализации очередей с приоритетом.

Применение свойства кучи

Свойство кучи лежит в основе нескольких важных алгоритмов и структур данных:

Пирамидальная сортировка (heapsort)

Алгоритм сортировки, использующий max-кучу. Сначала из входного массива строится max-куча (за O(n)). Затем многократно извлекается корень (максимальный элемент) и помещается в конец отсортированной части массива. После каждого извлечения свойство кучи восстанавливается. Время работы — O(n log n) в худшем, среднем и лучшем случаях. Heapsort является сортировкой на месте (in-place) и не требует дополнительной памяти.

Очередь с приоритетом (priority queue)

Структура данных, в которой каждый элемент имеет приоритет. Очередь с приоритетом обычно реализуется на основе min-кучи или max-кучи. Операции:

• insert: добавление элемента с заданным приоритетом.
• extract_min (или extract_max): удаление и возврат элемента с наименьшим (наибольшим) приоритетом.
• decrease_key: уменьшение приоритета элемента (важно в алгоритме Дейкстры).

Очереди с приоритетом используются в операционных системах для планирования задач, в сетевых протоколах для управления трафиком, в алгоритмах поиска кратчайших путей (Дейкстра, A*), в алгоритмах сжатия данных (кодирование Хаффмана).

Алгоритм Дейкстры

Алгоритм для нахождения кратчайших путей от одной вершины до всех остальных в графе с неотрицательными весами рёбер. В классической реализации используется очередь с приоритетом на основе min-кучи. Свойство кучи позволяет быстро извлекать вершину с наименьшим текущим расстоянием, что обеспечивает эффективность алгоритма — O((V+E) log V), где V — количество вершин, E — количество рёбер.

Кодирование Хаффмана

Алгоритм сжатия данных, использующий min-кучу для построения оптимального префиксного кода. На каждом шаге из кучи извлекаются два узла с наименьшими частотами, объединяются в новый узел, который вставляется обратно в кучу. Свойство кучи гарантирует, что на каждом шаге выбираются именно наименьшие частоты.

Свойство кучи в теории графов

Понятие свойства кучи также используется в теории графов при анализе структур данных, основанных на деревьях. В частности, свойство кучи является частным случаем более общего понятия «свойства упорядоченности по куче» (heap-ordered property), которое может быть применено к различным типам деревьев, не обязательно бинарным.

Критика и ограничения

Несмотря на широкую распространённость, свойство кучи имеет ряд ограничений:

• Отсутствие глобальной упорядоченности: свойство кучи не гарантирует, что элементы будут отсортированы по возрастанию или убыванию. Для полной сортировки требуется дополнительный алгоритм (например, heapsort).
• Неэффективность для поиска произвольного элемента: куча не поддерживает быстрый поиск элемента по значению (кроме корня). Для поиска необходимо просматривать все элементы, что занимает O(n).
• Сложность реализации слияния: для бинарных куч операция слияния двух куч требует O(n) времени, тогда как для биномиальных и фибоначчиевых куч она выполняется быстрее.

Примеры реализации

Реализация на языке C (max-куча)

```c

include <stdio.h>

include <stdlib.h>

define MAX_SIZE 100

typedef struct { int arr[MAX_SIZE]; int size; } MaxHeap;

void swap(int a, int b) { int temp = a; a = b; b = temp; }

void siftUp(MaxHeap *heap, int index) { while (index > 0 && heap->arr[index] > heap->arr[(index - 1) / 2]) { swap(&heap->arr[index], &heap->arr[(index - 1) / 2]); index = (index - 1) / 2; } }

void siftDown(MaxHeap heap, int index) { int largest = index; int left = 2 index + 1; int right = 2 * index + 2;

if (left < heap->size && heap->arr[left] > heap->arr[largest]) largest = left; if (right < heap->size && heap->arr[right] > heap->arr[largest]) largest = right; if (largest != index) { swap(&heap->arr[index], &heap->arr[largest]); siftDown(heap, largest); } }

void insert(MaxHeap *heap, int value) { if (heap->size >= MAX_SIZE) return; heap->arr[heap->size] = value; siftUp(heap, heap->size); heap->size++; }

int extractMax(MaxHeap *heap) { if (heap->size == 0) return -1; int max = heap->arr[0]; heap->arr[0] = heap->arr[heap->size - 1]; heap->size--; siftDown(heap, 0); return max; }

void buildHeap(MaxHeap heap, int arr, int n) { for (int i = 0; i < n; i++) heap->arr[i] = arr[i]; heap->size = n; for (int i = (n / 2) - 1; i >= 0; i--) siftDown(heap, i); } ```

Реализация на языке Python (min-куча с использованием модуля heapq)

В Python свойство кучи реализовано в стандартном модуле heapq, который предоставляет min-кучу.

```python import heapq

Создание пустой кучи

heap = []

Вставка элементов

heapq.heappush(heap, 5) heapq.heappush(heap, 3) heapq.heappush(heap, 8)

Извлечение минимального элемента

min_val = heapq.heappop(heap) # 3

Преобразование списка в кучу

arr = [9, 4, 7, 1, 6] heapq.heapify(arr) # arr теперь является min-кучей ```

Интересные факты

• В русскоязычной литературе термин «куча» для обозначения структуры данных был введён в 1970-х годах. До этого использовались термины «пирамида» или «двоичная пирамида». В частности, алгоритм heapsort в русских переводах часто назывался «пирамидальной сортировкой».
• Свойство кучи используется не только в информатике, но и в теории принятия решений, где кучи применяются для моделирования приоритетов в задачах планирования.
• В операционной системе Linux планировщик задач использует структуру данных, основанную на свойстве кучи, для управления очередями процессов с различными приоритетами.
• Свойство кучи является частным случаем более общего понятия «частичного порядка», что позволяет использовать кучи в задачах, где требуется только частичная упорядоченность данных.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание.
• Седжвик Р., Уэйн К. «Алгоритмы на Java» (Algorithms), 4-е издание.
• Кнут Д. Э. «Искусство программирования», том 3: «Сортировка и поиск».
• Вирт Н. «Алгоритмы и структуры данных».
• Документация Python: модуль heapq.