16. Куча
9 апреля 2026 г.
Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty
Куча - структура данных, представляющая собой полное бинарное дерево и удовлетворяющая следующему свойству: если узел N является потомком узла M, то значение ключа в узле (M) ≤ значения ключа в узле (N).
Благодаря этому свойству в корне дерева хранится максимум, но можно поменять в свойстве знак на ≥, тогда в корне будет хранится максимум.
Полным бинарным деревом называется дерево, у которого каждый узел имеет не более двух потомков, а заполнение уровней узлов идет в порядке сверху вниз (в пределах одного уровня – слева направо).
Ниже приведён пример минимальной кучи.
@font-face {
font-family: "Virgil";
src: url("https://excalidraw.com/Virgil.woff2");
}
@font-face {
font-family: "Cascadia";
src: url("https://excalidraw.com/Cascadia.woff2");
}
Основные операции для кучи: добавление элемента, извлечение минимума, а также операция, которая восстанавливает свойства кучи.
Операция добавления элемента
Новый элемент добавляется в конец массива.
При таком добавлении может нарушиться свойство кучи. Если свойство нарушается, то необходимо "поднимать" добавленный элемент (менять местами с вершиной родителем), пока свойство кучи не восстановиться.
Вычислительная сложность операции - .
Метод восстановления свойств кучи
Этот метод восстанавливает свойство кучи для дерева с корнем в i-ом узле. Для этого необходимо "опускать" i-ый узел (менять местами с наименьшим из детей), пока свойство кучи не будет восстановлено. Процесс остановится, когда не найдётся сына со значением меньше чем у родителя.
Вычислительная сложность операции - $O(log_2N)$.
Метод извлечения минимума из кучи
В куче минимум будет хранится в корне дерева, т. е. в первой ячейке массива (с индексом 0).
При извлечении минимума также может нарушиться свойство кучи. Восстановить его можно, поставив на место извлеченного минимума последний элемент кучи и вызвав для корня функцию восстановления свойств кучи, т. е. переупорядочить всё дерево (пример вызова функции указан выше).
Вычислительная сложность операции - .
В первой реализации мы будем хранить кучу в массиве.
Для узла с индексом i его левый и правый дети будут лежать в ячейках массива с индексами и соответственно.
Псевдокод
Аннотация: i - индекс элемента в куче left - индекс левого дочернего узла в куче right - индексы правого дочернего узла в куче largest - индекс самого большого элемента среди текущего узла и его дочерних узлов heap - массив, представляющий кучу swap - функция, используемая для обмена значениями двух элементов в куче heap - массив кучи min - минимальное значение в куче data - данные, которые добавляются в кучу j - индекс последнего элемента кучи parent - переменная, которая используется для хранения индекса родительского элемента в куче
Функция восстановления свойств кучи(i) вход в бесконечный цикл left <- 2 * i + 1 right <- 2 * i + 2 largest <- i если left < heap.size() и heap[left] < heap[largest] largest <- left если right < heap.size() и heap[right] < heap[largest] largest <- right если largest == i: выходим из цикла swap(heap[i], heap[largest]) index <- largest Функция извлечения минимума() если в heap есть элементы min <- heap[0] heap[0] удаляем последний элемент heap восстанавливаем свойства кучи Функция добавления элемента в кучу(data) добавляем data в heap parent <- (j - 1) / 2 пока j > 0 и heap[parent] > heap[j] swap(heap[j], heap[parent]) j <- parent parent = (j - 1) / 2
Реализация на Python
Аннотация: Node - класс элемента кучи data - данные, хранящиеся в элементе кучи priority - приоритет элемента кучи MinHeap - класс минимальной кучи heap - список, хранящий элементы кучи insert - функция, которая добавляет элемент в кучу i - индекс последнего элемента parent - родитель последнего элемента extract_min - функция, которая извлекает минимум root - корень кучи, минимум get_min - функция, которая получает минимальный элемент из кучи без его извлечения _heapify - функция, которая восстановливает свойства кучи left_child - индекс левого ребенка right_child - индекс правого ребенка size - функция, которая возвращает размер кучи
from typing import Callable, Generic, TypeVar, Any T = TypeVar('T') class Heap(Generic[T]): def __init__(self, key: Callable[[T], Any] | None = None): self.key = key self._heap = list() def __len__(self): return len(self._heap) def insert(self, value: T): self._heap.append(value) self._heapify_up(len(self._heap) - 1) def _heapify_up(self, index: int): parent_index = self._parent(index) while index > 0 and self._heap[index] < self._heap[parent_index]: self._heap[index], self._heap[parent_index] = self._heap[parent_index], self._heap[index] index = parent_index parent_index = self._parent(index) def _parent(self, index: int) -> int: return (index - 1) // 2 def _key_of(self, index: int) -> Any: if self.key is None: return self._heap[index] return self.key(self._heap[index]) def extract_min(self) -> None: if not self._heap: return if len(self._heap) == 1: self._heap.pop() return self._heap[0] = self._heap.pop() self._heapify_down(0) def _heapify_down(self, index: int): while True: left_child = 2 * index + 1 right_child = 2 * index + 2 smallest = index if ( left_child < len(self._heap) and self._key_of(left_child) < self._key_of(smallest) ): smallest = left_child if ( right_child < len(self._heap) and self._key_of(right_child) < self._key_of(smallest) ): smallest = right_child if smallest == index: return self._heap[index], self._heap[smallest] = self._heap[smallest], self._heap[index] index = smallest def _left(self, index: int) -> int: return 2 * index + 1 def _right(self, index: int) -> int: return 2 * index + 2 def get_min(self) -> T: if not self._heap: raise ValueError("Heap is empty") return self._heap[0]
Реализация кучи в библиотеке STL на C++
Аннотация: greater - функция сравнения, которая используется для сортировки элементов очереди с приоритетом в порядке убывания h - имя очереди push - метод добавления top - метод получения минимума из кучи pop - метод удаления верхнего элемента кучи
int main() { std::priority_queue<int, std::vector<int>, std::greater<int>> h; h.push(12); int min = h.top(); h.pop(); }
Олимпиадная реализация на C++
Аннотация: typedef - вектор целых чисел OlympicMinHeap - класс минимальной кучи add - метод добавления элемента в кучу get_min - метод возвращения минимального элемента в куче extract_min - метод извлечения минимального элемента в куче len - метод возвращения количества элементов в куче h - вектор целых чисел, используемый для реализации кучи heapify - метод, который используется для поддержания свойства кучи
typedef vector<int> vi; class OlympicMinHeap { public: void add(int v) { h.push_back(v); int idx = h.size() - 1; int p = (idx - 1) / 2; while (idx > 0 and h[p] > h[idx]) { swap(h[p], h[idx]); idx = p; p = (idx - 1) / 2; } } int get_min() { if (h.size() > 0) return h[0]; return NULL; } int extract_min() { if (h.size() > 0) { int root = h[0]; int j = h.size() - 1; h[0] = h[j]; h.erase(h.begin() + j); heapify(0); return root; } return NULL; } int len() return h.size(); private: vi h; void heapify(int idx) { while (true) { int l = 2 * idx + 1; int r = 2 * idx + 2; int larg = idx; if (l < h.size() && h[l] < h[larg]) larg = l; if (r < h.size() && h[r] < h[larg]) larg = r; if (larg == idx) return; swap(h[idx], h[larg]); idx = larg; } } };
Продуктовая реализация на C++
Аннотация: template - шаблон функции typename T - шаблонный тип данных параметра Node - класс элемента кучи priority - приоритет элемента data - данные, хранящиеся в элементе кучи MinHeap - класс минимальной кучи insert - метод добавления элемента в кучу heap - массив, в котором представлена куча parent - родитель последнего элемента get_min - метод, получающий минимальный элемент кучи без извлечения extract_min - метод извлечения минимума root - корень кучи, минимум idx_next_node - индекс следующего минимального элемента len - метод, который возвращает размер кучи heapify - метод, который восстанавливает свойства кучи
template <typename T> struct Node { int prioirity; T data; Node(int new_priority, T new_data) { data = new_data; prioirity = new_data; } }; template <typename T> class MinHeap { public: void insert(Node<T> value) { heap.push_back(value); int index = heap.size() - 1; int parent = (index - 1) / 2; while (index > 0 and heap[parent].prioirity > heap[index].prioirity) { std::swap(heap[parent], heap[index]); index = parent; parent = (index - 1) / 2; } } T get_min() { if (heap.size() > 0) { return heap[0].data; } return -1; } T extract_min() { if (heap.size() > 0) { Node<T> root = heap[0]; int idx_next_node = heap.size() - 1; heap[0] = heap[idx_next_node]; heap.erase(heap.begin() + idx_next_node); heapify(0); return root.data; } return -1; } int len() { return heap.size(); } private: std::vector<Node<T>> heap; void heapify(int index) { while (true) { int left = 2 * index + 1; int right = 2 * index + 2; int smallest = index; if (left < heap.size() && heap[left].prioirity < heap[smallest].prioirity) { smallest = left; } if (right < heap.size() && heap[right].prioirity < heap[smallest].prioirity) { smallest = right; } if (smallest == index) { return; } std::swap(heap[index], heap[smallest]); index = smallest; } } };
Во второй реализации мы напишем само дерево кучи. То есть, в ручную будем собирать дерево с помощью узлов.
Псевдокод
Аннотация: value - значение элемента, который добавляется в кучу node - узел дерева NULL - отсутствие элемента в куче min_value - минимальное значение root - корень дерева last_node - последний добавленный узел min_node - узел с минимальным значением
Функция добавления элемента(value) если в дереве кучи ещё нет элементов то корнем становится value иначе Функция вставки узла в дерево() Функция вставки узла в дерево(node) если у node нет левого потомка текущей узел становиться левым потомком node иначе если у node нет правого потомка текущей узел становиться правым потомком node иначе если все поддеревья заполнены Функция добавления узла(левый потомок) иначе Функция добавления узла(правый потомок) Функция балансировки() Функция балансировки(node) пока мы не дошли до корня и значение потомка < значения родителя меняем местами значения потомка и родителя меняем node на родителя node Функция извлечения минимума() если в куче нет элементов возвращаем NULL min_value <- root если у last_node нет родителя root <- NULL иначе если last_node был левым потомком удаляем левого потомка у родителя last_node иначе удаляем правого потомка у родителя last_node если last_node не равен root значение root <- значение last_node Функция восстановления свойств кучи(root) возвращаем min_value Функция восстановления свойств кучи(node) бесконечный цикл min_node <- node если у node есть левый потомок и его значение < значения min_node min_node <- левый потомок node если у node есть правый потомок и его значение < значения min_node min_node <- правый потомок node если min_node = node выходим из цикла меняем значения node и min_node node <- min_node
Реализация на Python
Аннотация: Node - класс для представления узла кучи MinHeap - класс минимальной кучи insert - метод добавления элемента в кучу new_node - новый узел _insert_recursively - методы вставки узла _balancing - метод корректировки значения кучи _is_complete - метод проверки заполненности дерева _get_height - метод получения высоты дерева extract_min - метод извлечения минимума _heapify - метод восстанавления свойства кучи _find_last_node - метод нахождения последнего добавленного элемента
class Node: def __init__(self, value): self.value = value self.parent = None self.left = None self.right = None class MinHeap: def __init__(self): self._root = None def insert(self, value): new_node = Node(value) if self._root is None: self._root = new_node else: self._insert_recursively(self._root, new_node) def _insert_recursively(self, node, new_node): if node.left is None: node.left = new_node new_node.parent = node elif node.right is None: node.right = new_node new_node.parent = node else: if self._is_complete(node.left, node.right): self._insert_recursively(node.left, new_node) else: self._insert_recursively(node.right, new_node) self._balancing(new_node) def _is_complete(self, left_node, right_node): if right_node is None: return True left_height = self._get_height(left_node) right_height = self._get_height(right_node) return left_height == right_height def _get_height(self, node): if node is None: return 0 left_height = self._get_height(node.left) right_height = self._get_height(node.right) return max(left_height, right_height) + 1 def _balancing(self, node): while node.parent is not None and node.value < node.parent.value: node.value, node.parent.value = node.parent.value, node.value node = node.parent def extract_min(self): if self._root is None: return None min_value = self._root.value last_node = self._find_last_node() if last_node.parent is None: self._root = None elif last_node.parent.left == last_node: last_node.parent.left = None else: last_node.parent.right = None if last_node != self._root and self._root is not None: self._root.value = last_node.value self._heapify(self._root) return min_value def _heapify(self, node): while True: min_node = node if node.left is not None and node.left.value < min_node.value: min_node = node.left if node.right is not None and node.right.value < min_node.value: min_node = node.right if min_node == node: break node.value, min_node.value = min_node.value, node.value node = min_node def _find_last_node(self): current_node = self._root while current_node.left is not None or current_node.right is not None: if current_node.left is not None: current_node = current_node.left else: current_node = current_node.right return current_node
Олимпиадная реализация на C++
Аннотация: typedef - переопределение имени типа данных Node - класс, представляющий узел в двоичном дереве v - значение узла p - родительский узел l - левый дочерний узел r - правый дочерний узел Heap - класс, реализующий двоичную кучу insert - метод добавления элемента в кучу complet - метод, проверяющий, является ли дерево полным get_h - метод, возвращающий высоту узла balanc - метод, балансирующий кучу heapify - метод, восстанавливающий свойства кучи find_min_n - метод, находящий узел с минимальным значением root - корень кучи extract_min - метод, извлекающий минимальный элемент из кучи
typedef vector<int> vi; class Node { public: int v; Node* p; Node* l; Node* r; Node(int v) { this->v = v; this->p = nullptr; this->l = nullptr; this->r = nullptr; } }; class Heap { private: void insert_(Node* n, Node* new_n) { if (n->l == nullptr) { n->l = new_n; new_n->p = n; } else if (n->r == nullptr) { n->r = new_n; new_n->p = n; } else { if (this->complet(n->l, n->r)) this->insert_(n->l, new_n); else this->insert_(n->r, new_n); } this->balanc(new_n); } bool complet(Node* l_n, Node* r_n) { if (r_n == nullptr) return true; int l_h = this->get_h(l_n); int r_h = this->get_h(r_n); return l_h == r_h; } int get_h(Node* n) { if (n == nullptr) return 0; int l_h = this->get_h(n->l); int r_h = this->get_h(n->r); return max(l_h, r_h) + 1; } void balanc(Node* n) { while (n->p != nullptr && n->v < n->p->v) { swap(n->v, n->p->v); n = n->p; } } void heapify(Node* n) { while (true) { Node* min_n = n; if (n->l != nullptr && n->l->v < min_n->v) min_n = n->l; if (n->r != nullptr && n->r->v < min_n->v) min_n = n->r; if (min_n == n) break; swap(n->v, min_n->v); n = min_n; } } Node* find_min_n() { Node* curr_n = this->root; while (curr_n->l != nullptr || curr_n->r != nullptr) { if (curr_n->l != nullptr) curr_n = curr_n->l; else curr_n = curr_n->r; } return curr_n; } public: Node* root; Heap() this->root = nullptr; void insert(int v) { Node* new_n = new Node(v); if (this->root == nullptr) this->root = new_n; else this->insert_(this->root, new_n); } int extract_min() { if (this->root == nullptr) return NULL; int min_v = this->root->v; Node* min_n = this->find_min_n(); if (min_n->p == nullptr) this->root = nullptr; else if (min_n->p->l == min_n) min_n->p->l = nullptr; else min_n->p->r = nullptr; if (min_n != this->root and this->root != nullptr) { this->root->v = min_n->v; this->heapify(this->root); } return min_v; } };
Продуктовая реализация на C++
Аннотация: Node - класс для представления узла кучи MinHeap - класс минимальной кучи insert_private - вставка узла balancing - корректирует значения кучи is_complete - проверка заполненности дерева get_height - подсчет высоты дерева heapify - восстановление свойств кучи find_min_node - функция поиска последнего добавленного элемента insert - добавление элемента в кучу extract_min - извлечение минимума
template <typename T> class Node { public: T value; Node* parent; Node* left; Node* right; Node(T value) { this->value = value; this->parent = nullptr; this->left = nullptr; this->right = nullptr; } }; template <typename T> class MinHeap { private: void insert_private(Node<T>* node, Node<T>* new_node) { if (node->left == nullptr) { node->left = new_node; new_node->parent = node; } else if (node->right == nullptr) { node->right = new_node; new_node->parent = node; } else { if (this->is_complete(node->left, node->right)) { this->insert_private(node->left, new_node); } else { this->insert_private(node->right, new_node); } } this->balancing(new_node); } bool is_complete(Node<T>* left_node, Node<T>* right_node) { if (right_node == nullptr) { return true; } int left_height = this->get_height(left_node); int right_height = this->get_height(right_node); return left_height == right_height; } int get_height(Node<T>* node) { if (node == nullptr) { return 0; } int left_height = this->get_height(node->left); int right_height = this->get_height(node->right); return std::max(left_height, right_height) + 1; } void balancing(Node<T>* node) { while (node->parent != nullptr && node->value < node->parent->value) { std::swap(node->value, node->parent->value); node = node->parent; } } void heapify(Node<T>* node) { while (true) { Node<T>* min_node = node; if (node->left != nullptr && node->left->value < min_node->value) { min_node = node->left; } if (node->right != nullptr && node->right->value < min_node->value) { min_node = node->right; } if (min_node == node) { break; } std::swap(node->value, min_node->value); node = min_node; } } Node<T>* find_min_node() { Node<T>* current_node = this->root; while (current_node->left != nullptr || current_node->right != nullptr) { if (current_node->left != nullptr) { current_node = current_node->left; } else { current_node = current_node->right; } } return current_node; } public: Node<T>* root; MinHeap() { this->root = nullptr; } void insert(T value) { Node<T>* new_node = new Node<T>(value); if (this->root == nullptr) { this->root = new_node; } else { this->insert_private(this->root, new_node); } } int extract_min() { if (this->root == nullptr) { return NULL; } int min_value = this->root->value; Node<T>* min_node = this->find_min_node(); if (min_node->parent == nullptr) { this->root = nullptr; } else if (min_node->parent->left == min_node) { min_node->parent->left = nullptr; } else { min_node->parent->right = nullptr; } if (min_node != this->root and this->root != nullptr) { this->root->value = min_node->value; this->heapify(this->root); } return min_value; } };