|
|
Описание структуры данных "очередь по приоритетам" и ее реализация на базе многопозиционного частично упорядоченного полного дерева.
Именно для решения различных задач на графах были разработаны эффективные реализации структуры данных "очередь по приоритетам". Очередь по приоритетам должна поддерживать следующие операции:
1. вставить в очередь
2. убрать из очереди минимальный элемент
3. изменить (уменьшить) приоритет элемента
Часто также необходимы различные вспомогательные операции: инициализация, проверка на пустоту и так далее.
Простейшая реализация очередей по приоритетам на базе неупорядоченного массива не позволяет производить достаточно быстро операцию "убрать из очереди минимальный элемент" и "изменить приоритет элемента". Обе эти операции будут работать за время пропорциональное количеству элементов в очереди, то есть за O(N). Существует несколько методов реализовать эти операции намного быстрей. Наиболее простой, но в то же время эффективный, это использования многопозиционных частично упорядоченных полных деревьев (такие деревья являются обобщением двоичных полных деревьев). При использовании таких деревьев все операции выполняются за время logdN, что является несомненным улучшением, так как функция логарифм растет довольно медленно. Основание логарифма обычно выбирают от 2 до 5: чем большее это число, тем меньше высота дерева, но тем больше приходиться делать операций для каждого элемента.
|
|