Открыть сервис
Главная → Блог → Извлечение минимума

Извлечение минимума

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

Определение и принцип работы

Извлечение минимума (extract-min) — это одна из основных операций над кучей, наряду с вставкой нового элемента и просмотром минимального элемента (find-min). В куче, организованной по принципу «родитель меньше или равен потомкам» (min-heap), минимальный элемент всегда находится в корне дерева. Операция извлечения минимума состоит из двух этапов: сохранение значения корневого элемента и его удаление с последующим восстановлением свойства кучи.

Алгоритм выполнения

  1. Сохранение корневого элемента: минимальный элемент (корень) копируется для последующего возврата.
  2. Замена корня: последний элемент кучи (наиболее правый на нижнем уровне) перемещается на место корня. Размер кучи уменьшается на единицу.
  3. Восстановление свойства кучи: выполняется процедура «просеивания вниз» (heapify-down или sift-down). Новый корень сравнивается со своими потомками; если он больше хотя бы одного из них, то меняется местами с наименьшим из потомков. Процесс повторяется, пока элемент не займёт правильную позицию, удовлетворяющую свойству кучи.

Временная сложность

В двоичной куче высота дерева составляет O(log n), где n — количество элементов. Операция извлечения минимума требует O(log n) времени, так как на каждом уровне выполняется не более одного сравнения и обмена. Вставка нового элемента также требует O(log n) времени, а просмотр минимального элемента — O(1).

Реализация в двоичной куче

Двоичная куча обычно реализуется на основе массива. Для удобства индексация часто начинается с единицы, хотя возможна и нулевая. В массиве для элемента с индексом i его левый потомок имеет индекс 2i, правый — 2i+1, а родитель — i/2 (целочисленное деление).

Псевдокод

``` function extractMin(heap): if heap.size == 0: return error min = heap[1] heap[1] = heap[heap.size] heap.size = heap.size - 1 heapifyDown(heap, 1) return min

function heapifyDown(heap, i): left = 2 i right = 2 i + 1 smallest = i if left <= heap.size and heap[left] < heap[smallest]: smallest = left if right <= heap.size and heap[right] < heap[smallest]: smallest = right if smallest != i: swap(heap[i], heap[smallest]) heapifyDown(heap, smallest) ```

Пример на языке C

```c

include <stdio.h>

include <stdlib.h>

typedef struct { int *arr; int size; int capacity; } MinHeap;

MinHeap createHeap(int capacity) { MinHeap heap = (MinHeap)malloc(sizeof(MinHeap)); heap->arr = (int)malloc(capacity * sizeof(int)); heap->size = 0; heap->capacity = capacity; return heap; }

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

void heapifyDown(MinHeap heap, int i) { int smallest = i; int left = 2 i + 1; int right = 2 * i + 2;

if (left < heap->size && heap->arr[left] < heap->arr[smallest]) smallest = left; if (right < heap->size && heap->arr[right] < heap->arr[smallest]) smallest = right; if (smallest != i) { swap(&heap->arr[i], &heap->arr[smallest]); heapifyDown(heap, smallest); } }

int extractMin(MinHeap *heap) { if (heap->size <= 0) return -1; // ошибка int root = heap->arr[0]; heap->arr[0] = heap->arr[heap->size - 1]; heap->size--; heapifyDown(heap, 0); return root; } ```

Применение

Алгоритм сортировки (Heapsort)

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

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

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

Алгоритм Прима

Для построения минимального остовного дерева графа извлечение минимума применяется для выбора ребра с наименьшим весом, соединяющего текущее дерево с ещё не включённой вершиной. Реализация на основе кучи обеспечивает сложность O(E log V).

Планирование задач

В операционных системах и системах реального времени приоритетные очереди, реализованные на кучах, используются для управления задачами. Извлечение минимума позволяет выбрать задачу с наивысшим приоритетом (наименьшим числовым значением) для выполнения.

Разновидности и модификации

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

В биномиальной куче извлечение минимума требует объединения нескольких деревьев после удаления корня. Временная сложность — O(log n), но амортизированная — O(log n) в худшем случае.

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

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

Куча с поддержкой слияния

Некоторые реализации позволяют эффективно объединять две кучи. Извлечение минимума в таких структурах может потребовать дополнительных операций, но общая сложность остаётся логарифмической.

Ограничения и особенности

  • Пустая куча: попытка извлечения минимума из пустой кучи приводит к ошибке. В корректных реализациях предусмотрена проверка размера.
  • Неустойчивость: операция извлечения минимума не сохраняет относительный порядок элементов с одинаковыми ключами. Если требуется устойчивость, необходимо использовать дополнительные механизмы (например, хранение времени вставки).
  • Память: после извлечения элемента размер кучи уменьшается, но выделенная память не освобождается автоматически. Для экономии памяти может потребоваться периодическая переаллокация.

Источники

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы