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

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

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

♦ Insert(H, v) вставляет элемент v в кучу H. Если куча в данный момент содержит n элементов, операция выполняется за время О(log n).

♦ FindМin(H) находит наименьший элемент кучи H, но не удаляет его. Операция выполняется за время О(1).

♦ Delete(Я, i) удаляет элемент в позиции i. Для кучи, содержащей n элементов, операция выполняется за время О(log n).

♦ ExtractMin(Я) находит и удаляет из кучи элемент с наименьшим значением клю- ча. Она объединяет две предыдущие операции, а следовательно, выполняется за время О(log n).

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

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

♦ Для удаления элемента v применяется операция Delete(Я,Position[v]). Создание массива не увеличивает общее время выполнения, поэтому удаление элемента v из кучи с n узлами выполняется за время О(log n).

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Приоритетность российской кино- и видеопродукции.
  2. Правило приоритетности цели сообщения.
  3. Наряды вне очереди
  4. 2. Наследники иных (последующих) очередей
  5. 1. Наследники первой очереди
  6. Статья 1263. Третья очередь наследников по закону
  7. Статья 1264. Четвертая очередь наследников по закону
  8. Статья 1265. Пятая очередь наследников по закону
  9. Статья 1262. Вторая очередь наследников по закону
  10. Статья 1261. Первая очередь наследников по закону
  11. Мудрец, в первую очередь, – гармоничный человек