Главная » Справочник » Алгоритмы. Разработка и применение » Реализация приоритетной очереди на базе кучи

Реализация приоритетной очереди на базе кучи

Структура данных кучи с операциями Heapify-down и Heapify-up позволяет эф- фективно реализовать приоритетную очередь, которая в любой момент времени содержит не более N элементов. Ниже приводится сводка операций, которые мы будем использовать.

StartHeap(N) возвращает пустую кучу H, настроенную для хранения не более N элементов. Операция выполняется за время O(N), так как в ней инициализи- руется массив, используемый для хранения кучи.
Insert(H, v) вставляет элемент v в кучу H. Если куча в данный момент содержит

n элементов, операция выполняется за время O(log n).

FindMin(H) находит наименьший элемент кучи H, но не удаляет его. Операция выполняется за время O(1).
Delete(H, i) удаляет элемент в позиции i. Для кучи, содержащей n элементов, операция выполняется за время O(log n).
ExtractMin(H) находит и удаляет из кучи элемент с наименьшим значением клю- ча. Она объединяет две предыдущие операции, а следовательно, выполняется за время O(log n).

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

Чтобы организовать эффективное обращение к нужным элементам приоритетной очереди, достаточно создать дополнительный массив Position, в котором хранится текущая позиция каждого элемента (каждого узла графа) в куче. С ним можно реализовать следующие операции.

Для удаления элемента v применяется операция Delete(H,Position[v]). Создание массива не увеличивает общее время выполнения, поэтому удаление элемента v из кучи с n узлами выполняется за время O(log n).
В некоторых алгоритмах также используется операция ChangeKey(H, v, α), кото- рая изменяет ключ элемента v новым значением key(v) = α. Чтобы реализовать эту позицию за время O(log n), необходимо сначала определить позицию v в массиве, что делается при помощи массива Position. После определения пози- ции элемента v мы изменяем его ключ, а затем применяем процедуру Heapify-up или Heapify-down в зависимости от ситуации.