Изменения

Перейти к: навигация, поиск

Приоритетные очереди

12 байт убрано, 15:45, 7 июня 2015
Нет описания правки
'''Приоритетная очередь''' (англ. ''priority queue'') {{---}} это абстрактная структура данных на подобии стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они распологаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью '''куч''' (англ. ''heap'').
 
==Операции==
 
* <tex>\mathrm{findMin}</tex> или <tex>\mathrm{findMax}</tex> {{---}} поиск элемента с наибольшим приоритетом
* <tex>\mathrm{insert}</tex> или <tex>\mathrm{push}</tex> {{---}} вставка нового элемента
* <tex>\mathrm{increaseKey}</tex> или <tex>\mathrm{decreaseKey}</tex> {{---}} обновить значение элемента
* <tex>\mathrm{merge}</tex> {{---}} объединение двух приоритетных очередей
 
==Реализации==
===Наивная===
В качестве наивной реализации мы можем взять обычный список и при добавлении нового элемента класть его в конец, а при запросе элемента с максимальным приоритетом проходить по всему списку. Тогда операция <tex>\mathrm{insert}</tex> будет выполняться за <tex>O(1)</tex>, а <tex>\mathrm{extractMin}</tex> или <tex>\mathrm{extractMax}</tex> за <tex>O(n)</tex>.
 
===Обычная===
Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.
 
==Виды приорететных очередей==
 
{| class="wikitable"
|-
|-
|}
 
==Применение==
Приоритетные очереди используются в следующих алгоритмах: [[алгоритм Дейкстры]], [[алгоритм Прима]], дискретно-событийное моделирование (англ. ''discrete-event simulation, DES''), [[алгоритм Хаффмана]], поиск по первому наилучшему совпадению, управление полосой пропускания.
 
==Реализации в языках программирования==
* [http://en.cppreference.com/w/cpp/container Стандартная библиотека шаблонов] (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
* В Perl имеются [http://metacpan.org/pod/Heap реализации] бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
* Go имеет пакет [http://golang.org/pkg/container/heap/ heap], в котором реализованы алгоритмы для работы с кучами.
 
 
 
== Источники информации ==
* [http://en.wikipedia.org/wiki/Heap_(data_structure) Wikidedia {{---}} Heap (data structure)]
* [http://en.wikipedia.org/wiki/D-ary_heap Wikidedia {{---}} <tex>d</tex>-ary heap]
* [http://en.wikipedia.org/wiki/Fibonacci_heap Wikidedia {{---}} Fibonacci heap]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
48
правок

Навигация