Задача

В реализации алгоритма устойчивых паросочетаний (см. раздел 2.3) упоминалась необходимость поддержания динамически изменяемого множества S (множества всех свободных мужчин в данном примере). В такой ситуации мы хотим иметь воз- можность добавлять и удалять элементы из S, а также выбрать элемент из S, когда этого потребует алгоритм.
Приоритетная очередь предназначена для приложений, в которых элементам назначается приоритет (ключ), и каждый раз, когда потребу- ется выбрать элемент из S, должен выбираться элемент с наивысшим приоритетом.

Приоритетная очередь представляет собой структуру данных, которая под- держивает множество элементов S. С каждым элементом v S связывается ключ key(v), определяющий приоритет элемента v; меньшие ключи представляют более высокие приоритеты. Приоритетные очереди поддерживают добавление и удаление элементов из очереди, а также выбор элемента с наименьшим ключом. В нашей реализации приоритетных очередей также будут поддерживаться допол- нительные операции, краткая сводка которых приведена в конце раздела.

Основная область применения приоритетных очередей, которая обязательно должна учитываться при обсуждении их общих возможностей, — задача управ- ления событиями реального времени (например, планирование выполнения про- цессов на компьютере). Каждому процессу присваивается некоторый приоритет, но порядок поступления процессов не совпадает с порядком их приоритетов. Вместо этого имеется текущее множество активных процессов; мы хотим иметь возможность извлечь процесс с наивысшим приоритетом и активизировать его. Множество процессов можно представить в виде приоритетной очереди, в которой ключ процесса представляет величину приоритета. Планирование процесса с наи- высшим приоритетом соответствует выбору из приоритетной очереди элемента с наименьшим ключом; параллельно новые процессы должны вставляться в оче- редь по мере поступления в соответствии со значениями приоритетов.

На какую эффективность выполнения операций с приоритетной очередью можно рассчитывать? Мы покажем, как реализовать приоритетную очередь, ко- торая в любой момент времени содержит не более n элементов, с возможностью добавления и удаления элементов и выбора элемента с наименьшим ключом за время О(log n).

Прежде чем переходить к обсуждению реализации, рассмотрим очень простое применение приоритетных очередей. Оно демонстрирует, почему время О(log n) на операцию является «правильной» границей, к которой следует стремиться.

(2.11) Последовательность из O(n) операций приоритетной очереди может ис- пользоваться для сортировки множества из n чисел.

Доказательство. Создадим приоритетную очередь H и вставим каждое число в H, используя его значение в качестве ключа. Затем будем извлекать наименьшие числа одно за другим, пока не будут извлечены все числа; в результате полученная последовательность чисел будет отсортирована по порядку. ■

Итак, с приоритетной очередью, способной выполнять операции вставки и извлечения минимума с временем О(log n) за операцию, можно отсортировать n чисел за время O(n log n). Известно, что в модели вычислений на базе срав- нений (при которой каждая операция обращается к входным данным только посредством сравнивания пары чисел) время, необходимое для сортировки, должно быть пропорционально как минимум n log n, так что (2.11) поясняет, что в некотором смысле время О(log n) на операцию — лучшее, на что можно рассчи- тывать. Следует отметить, что реальная ситуация немного сложнее: реализации приоритетных очередей более сложные, чем представленная здесь, могут улуч- шать время выполнения некоторых операций и предоставлять дополнительную функциональность. Но из (2.11) следует, что любая последовательность операций приоритетной очереди, приводящая к сортировке n чисел, должна занимать вре- мя, пропорциональное по меньшей мере n log n.

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

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения
  18. Задачи
  19. Трудная задача
  20. 1.1. Предмет и задачи криминалистики