Куча (двоичная куча)
Последнее обновление
Двоичная куча - это полное двоичное дерево, которое держит наименьшее (min-heap) или наибольшее (max-heap) значение в корне. Эта визуализация - min-heap: каждый родитель меньше или равен своим потомкам. Чтобы добавить значение, его помещают в следующую свободную позицию, а затем «поднимают вверх», меняя местами с родителем, пока оно меньше, пока свойство кучи снова не выполнится. Нажмите воспроизведение выше, чтобы увидеть, как каждое новое значение всплывает на своё место.
Поскольку куча - это полное дерево, она компактно хранится в массиве: потомки узла i находятся в 2i+1 и 2i+2. Вставка и удаление минимума - O(log n) (один путь от корня к листу), а просмотр минимума - O(1), что и нужно очереди с приоритетом.
Временная и пространственная сложность
| Операция | Сложность | Примечания |
|---|---|---|
| Просмотр мин/макс | O(1) | Это всегда корень |
| Вставка (push) | O(log n) | Всплытие по одному пути |
| Удаление мин/макс | O(log n) | Погружение по одному пути |
| Построение кучи | O(n) | Heapify за один раз |
| Память | O(n) | На основе массива, без указателей |
Пошагово (push)
| Шаг | Что происходит |
|---|---|
| 1 | Добавьте новое значение в конец (следующий свободный лист). |
| 2 | Сравните его с родителем. |
| 3 | Если оно меньше (min-heap), поменяйте его вверх. |
| 4 | Повторяйте, пока оно не перестанет быть меньше родителя или не достигнет корня. |
Разобранный пример
Построение min-heap путём вставки [5, 3, 8, 1, 4] по одному значению за раз:
| Push | Массив после всплытия | Действие |
|---|---|---|
5 | [5] | Первое значение становится корнем. |
3 | [3, 5] | 3 < родителя 5, поэтому всплывает до корня. |
8 | [3, 5, 8] | 8 > родителя 5, поэтому остаётся листом. |
1 | [1, 3, 8, 5] | 1 < родителя 5, обмен; затем 1 < родителя 3, всплывает до корня. |
4 | [1, 3, 8, 5, 4] | 4 > родителя 3, поэтому остаётся; минимум 1 остаётся в корне. |
Когда использовать кучу
| Используйте, когда | Избегайте, когда |
|---|---|
| Вам многократно нужен наименьший или наибольший элемент из меняющегося набора. | Нужно искать произвольные значения, а не только крайний - используйте BST или хеш-множество. |
| Вы реализуете очередь с приоритетом для Dijkstra, A* или планировщика. | Данные нужно всё время держать полностью отсортированными. |
Вы хотите вставку и удаление минимума за O(log n) с компактным массивом. | Нужен быстрый поиск или удаление конкретного (не корневого) элемента. |
| Нужно объединить поток элементов и извлекать их по приоритету. | Набор данных крошечный, и линейный проход проще и достаточно быстр. |
Код Heap (Priority Queue)
Чистая, готовая к запуску реализация Heap (Priority Queue) на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Heap (Priority Queue) на Python
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])Код Heap (Priority Queue) на JavaScript
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Код Heap (Priority Queue) на Java
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}Код Heap (Priority Queue) на C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}Код Heap (Priority Queue) на C
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}Частые вопросы о кучах
Для чего используется куча?
Кучи реализуют очереди с приоритетом, на которых работают алгоритм кратчайшего пути Дейкстры, планировщики задач и симуляции событий. Они также являются движком heapsort. Каждый раз, когда вам многократно нужен наименьший или наибольший элемент из меняющегося набора, куча - подходящий инструмент.
В чём разница между кучей и двоичным деревом поиска?
Оба - двоичные деревья, но BST поддерживает полный порядок слева направо (что позволяет упорядоченный поиск), тогда как куча гарантирует лишь отношение родитель-потомок (мин или макс в корне). Куча даёт доступ O(1) к крайнему значению; BST даёт поиск O(log n) любого значения.
Почему куча хранится в массиве?
Поскольку куча всегда является полным двоичным деревом, её узлы идеально отображаются на индексы массива: потомки индекса
i находятся в 2i+1 и 2i+2, а родитель - в (i-1)/2. Это избавляет от хранения указателей на потомков и даёт отличную производительность кеша.Куча - это то же самое, что отсортированный массив?
Нет. Куча гарантирует только то, что каждый родитель меньше (min-heap) или больше (max-heap) своих потомков, поэтому братья и двоюродные узлы не имеют определённого порядка. Отсортированный массив полностью упорядочен, но вставка в него стоит
O(n), тогда как куча вставляет за O(log n) и по-прежнему даёт мгновенный доступ к крайнему значению.Когда мне использовать кучу вместо простой сортировки массива?
Обращайтесь к куче, когда данные постоянно меняются и вам нужен только текущий минимум или максимум - вставка и извлечение стоят по
O(log n) каждая, против пересортировки всего массива. Если у вас статичный набор данных и нужны все элементы по порядку, одна сортировка O(n log n) проще и часто быстрее.Занимает ли построение кучи из n элементов O(n log n)?
Нет, если строить её за один раз. Вставка
n элементов по одному - O(n log n), но восходящий heapify, который погружает от последнего родителя к корню, выполняется в целом за O(n), потому что большинство узлов находятся у дна и погружаются лишь на короткое расстояние.Связанные ресурсы
Больше визуализаций
