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

Структура данных кучи с операциями 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 в зависимости от ситуации.