Структура данных — куча

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


Определение и хранение кучи

Куча — структура максимальной кучи и хранение в массиве

Представление в виде дерева (максимальная куча)

15Индекс 0
10Индекс 1
8Индекс 2
53
34
25

Представление массива (компактное хранение)

15
[0]
10
[1]
8
[2]
5
[3]
3
[4]
2
[5]

Родитель: (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)

Пример

#include <stdio.h>

#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 наибольших элементов
Другие расширения