Изменения
→Виды приоритетных очередей
'''Приоритетная очередь''' (англ. ''priority queue'') {{---}} это абстрактная структура данных на подобии наподобие стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они распологаются располагаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью '''куч''' (англ. ''heap'').
==Операции==
Приоритетные очереди поддерживают следующие операции:
===Обычная===
Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.
==Виды приорететных приоритетных очередей==
{| class="wikitable"
|-
|-
| [[Биномиальная куча]]
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1\log n)</tex>| align="center" | <tex>O(\log n)</tex>
| [[Биномиальная куча]] (англ. ''binomial heap'') {{---}} структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:
* ключ каждой вершины не меньше ключа ее родителя
| [[Тонкая куча]] (англ. ''thin heap'') {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
|-
| [[Фибоначчиева Сонная куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
|-
|}
==Применение==
Приоритетные очереди используются в следующих алгоритмах: [[алгоритм Дейкстры]], [[алгоритм Прима]], дискретно-событийное моделирование (англ. ''discrete-event simulation, DES'')<ref>[http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE-%D1%81%D0%BE%D0%B1%D1%8B%D1%82%D0%B8%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Wikipedia {{---}} Дискретно-событийное моделирование]</ref>, [[алгоритм Хаффмана]], поиск по первому наилучшему совпадению, управление полосой пропускания.
<references />
== Источники информации ==
* [http://en.wikipedia.org/wiki/Heap_(data_structure) Wikidedia Wikipedia {{---}} Heap (data structure)]* [http://en.wikipedia.org/wiki/2%E2%80%933_heap Wikidedia Wikipedia {{---}} 2-3 heap]* [http://en.wikipedia.org/wiki/Beap Wikidedia Wikipedia {{---}} Beap]* [http://en.wikipedia.org/wiki/Binary_heap Wikidedia Wikipedia {{---}} Binary heap]* [http://en.wikipedia.org/wiki/Binomial_heap Wikidedia Wikipedia {{---}} Binomial heap]* [http://en.wikipedia.org/wiki/Brodal_queue Wikidedia Wikipedia {{---}} Brodal queue]* [http://en.wikipedia.org/wiki/D-ary_heap Wikidedia Wikipedia {{---}} <tex>d</tex>-ary heap]* [http://en.wikipedia.org/wiki/Fibonacci_heap Wikidedia Wikipedia {{---}} Fibonacci heap]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
