Структура данных для реализации приоритетной очереди

Для реализации приоритетной очереди мы воспользуемся структурой данных, называемой кучей (heap). Прежде чем обсуждать организацию кучи, следует рас- смотреть, что происходит при более простых, более естественных подходах к реа- лизации функций приоритетной очереди.
Например, можно объединить элементы в список и завести отдельный указатель Min на элемент с наименьшим ключом. Это упрощает добавление новых элементов, но с извлечением минимума возникают сложности. Найти минимум несложно (просто перейти по указателю Min), но после удаления минимального элемента нужно обновить Min для следующей операции, а для этого потребуется просканировать все элементы за время O(n) для нахожде- ния нового минимума.

Это усложнение наводит на мысль, что элементы стоило бы хранить в порядке сортировки ключей. Такая структура упростит извлечение элемента с наимень- шим ключом, но как организовать добавление новых элементов? Может, стоит хранить элементы в массиве или в связанном списке? Допустим, добавляется эле- мент 5 с ключом key(5). Если множество S хранится в отсортированном массиве, можно воспользоваться бинарным поиском для нахождения в массиве позиции вставки 5 за время О(log n), но для вставки 5 в массив все последующие элементы необходимо сдвинуть на одну позицию вправо. Сдвиг займет время O(n). С дру- гой стороны, если множество хранится в двусвязном отсортированном списке, вставка в любой позиции выполняется за время O(1), но двусвязный список не поддерживает бинарный поиск, поэтому для поиска позиции вставки 5 может потребоваться время до O(n).

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

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

  1. 3. Использование программ для ЭВМ, баз данных и топологий ИМС третьими лицами
  2. 5.2.7. Люди, необходимые для реализации проекта или цели
  3. Свободное воспроизведение программ для ЭВМ и баз данных. Декомпилирование программ для ЭВМ
  4. § 6. Авторско-правовая охрана программ для ЭВМ, баз данных и топологий интегральных микросхем
  5. 1. Понятие программы для ЭВМ, базы данных и топологии интегральной микросхемы и основные правила их охраны
  6. 12.2.2. Правовое регулирование информационных отношений при производстве и распространении программ для ЭВМ и баз данных
  7. Приоритетность российской кино- и видеопродукции.
  8. Правило приоритетности цели сообщения.
  9. Молитва о Любви – для привлечения и полнейшей реализации Любви
  10. Упражнение для выявления структуры вашего характера
  11. Жизненная задача и высшее «Я» для оральной структуры
  12. 5.2.17. Укрепления благосостояния своих лучших сотрудников для увеличения функциональности всех элементов, составляющих структуру и архитектуру цели
  13. КРИТЕРИИ ОЦЕНКИ ПРОИЗВЕДЕНИЯ с ТОЧКИ ЗРЕНИЯ его ЖАНРОВО–ТЕМАТИЧЕСКОЙ СТРУКТУРЫ и ЗРИТЕЛЬСКОГО ВОСПРИЯТИЯ (для исследователей экранной продукции)
  14. Наряды вне очереди
  15. 1. Наследники первой очереди
  16. 2. Наследники иных (последующих) очередей
  17. Статья 1263. Третья очередь наследников по закону
  18. Статья 1264. Четвертая очередь наследников по закону
  19. Статья 1265. Пятая очередь наследников по закону
  20. Статья 1262. Вторая очередь наследников по закону