Алгоритмы и множества

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

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

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

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

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

Планирование процесса с наивысшим приоритетом соответствует выбору из приоритетной очереди элемента с наименьшим ключом; параллельно новые процессы должны вставляться в очередь по мере поступления в соответствии со значениями приоритетов.

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

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

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

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

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

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