Структуры данных и модели вычислений
Основные определения
Приоритетная очередь — это абстрактный тип данных, предназначенный для представления взвешенных множеств. Множество называется взвешенным, если каждому его элементу однозначно соответствует число, называемое ключом или весом. Основными операциями над приоритетной очередью являются следующие операции:
- ВСТАВИТЬ в множество новый элемент со своим ключом.
- НАЙТИ в множестве элемент с минимальным ключом. Если элементов с минимальным ключом несколько, то находится один из них. Найденный элемент не удаляется из множества.
- УДАЛИТЬ из множества элемент с минимальным ключом. Если элементов с минимальным ключом несколько, то удаляется один из них.
Дополнительные операции над приоритетными очередями:
- ОБЪЕДИНИТЬ два множества в одно.
- УМЕНЬШИТЬ ключ указанного элемента множества на заданное положительное число.
Приоритетная очередь естественным образом используется в таких задачах, как сортировка элементов массива, поиск во взвешенном неориентированном графе минимального остовного дерева, поиск кратчайших путей от заданной вершины взвешенного графа до его остальных вершин, и во многих других.
Приоритетную очередь можно представить с помощью массива или списка элементов, но такие реализации неэффективны по времени выполнения основных операций. Так, например, поиск элемента с минимальным ключом в неупорядоченном массиве или списке требует последовательного просмотра всех его элементов. Если поддерживать упорядоченность массива или списка по ключу, то "неудобной" окажется операция вставки нового элемента.
Чаще всего приоритетная очередь представляется с помощью корневого дерева или набора корневых деревьев с определенными свойствами. При этом узлам дерева ставятся во взаимно однозначное соответствие элементы рассматриваемого множества.
Соответствие между узлами дерева и элементами множества называется кучеобразным, если для каждого узла соблюдается следующее условие:
Ключ элемента, приписанного узлу , не превосходит ключей, приписанных его потомкам.
Такие представления взвешенных множеств называются кучами. Вид дерева и способ его представления в памяти компьютера подбирается в зависимости от тех операций, которые предполагается выполнять над множеством, и от того, насколько эти операции сказываются на суммарной трудоемкости алгоритма.
