Более сложная структура данных: приоритетная очередь

Наша основная цель в этой книге была представлена в начале главы: нас интере- суют алгоритмы, обеспечивающие качественный выигрыш по сравнению с поис- ком методом «грубой силы»; в общем случае этот критерий имеет конкретную формулировку разрешимости с полиномиальным временем.
Как правило, нахож- дение решения нетривиальной задачи с полиномиальным временем не зависит от мелких подробностей реализации, скорее различия между экспоненциальной и полиномиальной сложностью зависят от преодоления препятствий более высо- кого уровня. Но после разработки эффективного алгоритма решения задачи часто
бывает возможно добиться дополнительного улучшения времени выполнения за счет внимания к подробностям реализации, а иногда — за счет использования более сложных структур данных.

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

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

Еще по теме Более сложная структура данных: приоритетная очередь:

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