Структура данных — куча
Куча — это особая структура полного двоичного дерева, удовлетворяющая свойству упорядоченности кучи. Куча гарантирует только соотношение размеров между родительским и дочерними узлами и не требует строгого порядка между левым и правым поддеревьями.
Определение и хранение кучи
Представление в виде дерева (максимальная куча)
Представление массива (компактное хранение)
Родитель: (i-1)/2 | Левый потомок: 2i+1 | Правый потомок: 2i+2
Полное двоичное дерево → естественно подходит для массивов, без накладных расходов на указатели
Просеивание вверх (вставка) O(log n)
Поместите новый элемент в конец → сравните с родителем → поменяйте местами, если он больше → повторяйте до вершины кучи
Просеивание вниз (удаление корня) O(log n)
Переместите последний элемент в корень → сравните с большим потомком → поменяйте местами, если он меньше → повторяйте до листа
Два типа куч:
- Максимальная кучаКаждый родительский узел ≥ дочернего узла, корневой узел содержит максимальное значение
- Минимальная кучаКаждый родительский узел ≤ дочерний узел, корневой узел имеет минимальное значение
Поскольку куча — это полное двоичное дерево, она естественно подходит для хранения в массиве:
| Узел (индекс i) | Связь | Позиция (с нумерацией от 0) |
|---|---|---|
| Родительский узел | parent(i) | (i - 1) / 2 |
| Левый дочерний узел | left(i) | 2 * i + 1 |
| Правый дочерний узел | right(i) | 2 * i + 2 |
Вставка и удаление в куче (процесс heapify)
Пример
#define MAX 100
/* Структура максимальной кучи */
struct MaxHeap {
int arr[MAX];
int size; /* Текущее количество элементов */
};
void initHeap(struct MaxHeap* h) { h->size = 0; }
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Просеивание вверх: переместить только что вставленный элемент снизу вверх
Сравнить с родительским узлом; если больше родителя, поменять местами; повторять, пока порядок кучи не будет удовлетворён */
void siftUp(struct MaxHeap* h, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (h->arr[idx] <= h->arr[parent]) break;
swap(&h->arr[idx], &h->arr[parent]);
idx = parent;
}
}
/* Вставка: сначала поместите элемент в конец, затем скорректируйте с помощью просеивания вверх O(log n) */
void insert(struct MaxHeap* h, int value) {
if (h->size >= MAX) return;
h->arr[h->size] = value;
siftUp(h, h->size);
h->size++;
}
/* Просеивание вниз: корректировка от корня вниз
Сравните с большим дочерним узлом; если меньше, поменяйте местами; повторяйте, пока не будет соблюдён порядок кучи */
void siftDown(struct MaxHeap* h, int idx) {
while (1) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < h->size && h->arr[left] > h->arr[largest])
largest = left;
if (right < h->size && h->arr[right] > h->arr[largest])
largest = right;
if (largest == idx) break;
swap(&h->arr[idx], &h->arr[largest]);
idx = largest;
}
}
/* Удалить корень (максимальное значение): переместить последний элемент наверх, затем скорректировать с помощью sift-down O(log n) */
int extractMax(struct MaxHeap* h) {
if (h->size == 0) return -1;
int maxVal = h->arr[0];
h->arr[0] = h->arr[--h->size]; /* Переместить последний элемент наверх */
siftDown(h, 0); /* Корректировка просеиванием вниз */
return maxVal;
}
int main() {
struct MaxHeap h;
initHeap(&h);
int vals[] = {3, 10, 5, 8, 2, 15};
for (int i = 0; i < 6; i++) insert(&h, vals[i]);
printf("Извлечение максимальных значений по порядку: ");
while (h.size > 0) {
printf("%d ", extractMax(&h));
}
printf("\n"); /* Вывод: 15 10 8 5 3 2 (по убыванию) */
return 0;
}
Сценарии применения
| Сценарий | Описание |
|---|---|
| Приоритетная очередь | Куча — наиболее распространённая базовая реализация приоритетной очереди |
| Пирамидальная сортировка | Алгоритм сортировки на месте со сложностью O(n log n) (подробно в главе 18) |
| Задача Top K | Используйте минимальную кучу для поддержания K наибольших элементов |