48
правок
Изменения
Новая статья
'''Приоритетная очередь''' (англ. ''priority queue'') {{---}} это абстрактная структура данных на подобии стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они распологаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью куч (англ. ''heap'').
==Операции==
* find-min (find-max) - поиск элемента с наибольшим приоритетом
* insert (push) - вставка нового элемента
* extract-min (extract-max) - извлечь элемент с наибольшим приоритетом
* delete-min (delete-max) - удалить элемент с наибольшим приоритетом
* merge - объединение двух приоритетных очередей
==Реализации==
===Наивная===
В качестве наивной реализации мы можем взять обычный список и при добавлении нового элемента класть его в конец, а при запросе элемента с максимальным приоритетом проходить по всему списку. Тогда операция insert будет выполняться за <tex>O(1)</tex>, а extract-max (extract-min) за <tex>O(n)</tex>.
===Обычная===
Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.
==Виды приорететных очередей==
{| class="wikitable"
|-
! rowspan="2" | Название
! colspan="4" | Операции
! rowspan="2" | Описание
|-
| align="center" width="5%" | find-min
| align="center" | insert
| align="center" width="5%" | delete-min
| align="center" | merge
|-
| [[2-3 куча]]
| align="center" rowspan="11" | <tex>O(1)</tex>
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.
|-
| [[Биномиальная куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| [[Биномиальная куча]] (англ. ''binomial heap'') {{---}} структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:
* ключ каждой вершины не меньше ключа ее родителя
* все биномиальные деревья имеют разный размер
|-
| [[Куча Бродала-Окасаки]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| [[Куча Бродала-Окасаки]] (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.
|-
| [[Двоичная куча]]
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(m \log(n+m))</tex>
| [[Двоичная куча]] (англ. ''binary heap'') {{---}} такое двоичное дерево, для которого выполнены три условия:
*Значение в любой вершине не меньше, чем значения её потомков.
*Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
*Последний слой заполняется слева направо.
|-
| [[Двуродительская куча]]
| align="center" | <tex>O(\sqrt{n})</tex>
| align="center" | <tex>O(\sqrt{n})</tex>
| |
| [[Двуродительская куча]] (англ. ''bi-parental heap'' или ''beap'') {{---}} такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это не первый уровень). Структура позволяет производить сублиненый поиск.
|-
| [[d-арная куча| <tex>d</tex>-арная куча]]
| align="center" | <tex>O(\log n / \log d)</tex>
| align="center" | <tex>O(d\log n / \log d)</tex>
| align="center" | <tex>O(m \log(n+m) / \log d)</tex>
| [[d-арная куча| <tex>d</tex>-арная куча]] (англ. ''<tex>d</tex>-ary heap'') {{---}} [[двоичная куча]], в которой у каждого элемента <tex>d</tex> детей вместо <tex>2</tex>.
|-
| [[Левосторонняя куча]]
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| [[Левосторонняя куча]] (англ. ''leftist heap'') {{---}} двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи.
|-
| [[Спаренная куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| [[Спаренная куча]] (англ. ''pairing heap'') {{---}} куча с относительно простой реализацией и хорошей производительностью, может быть рассмотрена как упрощенная [[Фибоначчиева куча]].
|-
| [[Толстая куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| [[Толстая куча]] {{---}} это почти кучеобразный нагруженный лес.
|-
| [[Тонкая куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| [[Тонкая куча]] (англ. ''thin heap'') {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
|-
| [[Фибоначчиева куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| Куча, построенная на основе Фибоначчиева дерева. [[Фибоначчиево дерево]] (англ. ''Fibonacci tree'') {{---}} биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
|-
|}
==Применение==
* Алгоритм Дейкстры
* Алгоритм Прима
* Дискретно-событийное моделирование (англ. ''discrete-event simulation, DES'')
* Код Хаффмана
* Поиск по первому наилучшему совпадению
* Управление полосой пропускания
==Реализации в языках программирования==
* Стандартная библиотека шаблонов (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
* Библиотека Boost для C++ включает в себя библиотеку для работу с кучами. В отличии от STL, поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как [[Фибоначчиева куча]], [[Биномиальная куча]] и [[Спаренная куча]].
* В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе java.util.PriorityQueue<E>, который не поддерживает операции decrease-key и increase-key.
* Python имеет модуль heapq, который реализует очереди с приоритетами с помощью бинарной кучи.
* PHP имеет поддержку кучи на максимум (SplMaxHeap) и кучи на минимум (SplMinHeap), как часть Standard PHP Library начиная с версии 5.3.
* В Perl имеются реализации бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
* Go имеет пакет heap, в котором реализованы алгоритмы для работы с кучами.
== Источники информации ==
* [http://en.wikipedia.org/wiki/Heap_(data_structure)| Wikidedia {{---}} Heap (data structure)]
* [http://en.wikipedia.org/wiki/2%E2%80%933_heap| Wikidedia {{---}} 2-3 heap]
* [http://en.wikipedia.org/wiki/Beap| Wikidedia {{---}} Beap]
* [http://en.wikipedia.org/wiki/Binary_heap| Wikidedia {{---}} Binary heap]
* [http://en.wikipedia.org/wiki/Binomial_heap| Wikidedia {{---}} Binomial heap]
* [http://en.wikipedia.org/wiki/Brodal_queue| Wikidedia {{---}} Brodal queue]
* [http://en.wikipedia.org/wiki/D-ary_heap| Wikidedia {{---}} <tex>d</tex>-ary heap]
* [http://en.wikipedia.org/wiki/Fibonacci_heap| Wikidedia {{---}} Fibonacci heap]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
==Операции==
* find-min (find-max) - поиск элемента с наибольшим приоритетом
* insert (push) - вставка нового элемента
* extract-min (extract-max) - извлечь элемент с наибольшим приоритетом
* delete-min (delete-max) - удалить элемент с наибольшим приоритетом
* merge - объединение двух приоритетных очередей
==Реализации==
===Наивная===
В качестве наивной реализации мы можем взять обычный список и при добавлении нового элемента класть его в конец, а при запросе элемента с максимальным приоритетом проходить по всему списку. Тогда операция insert будет выполняться за <tex>O(1)</tex>, а extract-max (extract-min) за <tex>O(n)</tex>.
===Обычная===
Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.
==Виды приорететных очередей==
{| class="wikitable"
|-
! rowspan="2" | Название
! colspan="4" | Операции
! rowspan="2" | Описание
|-
| align="center" width="5%" | find-min
| align="center" | insert
| align="center" width="5%" | delete-min
| align="center" | merge
|-
| [[2-3 куча]]
| align="center" rowspan="11" | <tex>O(1)</tex>
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.
|-
| [[Биномиальная куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| [[Биномиальная куча]] (англ. ''binomial heap'') {{---}} структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:
* ключ каждой вершины не меньше ключа ее родителя
* все биномиальные деревья имеют разный размер
|-
| [[Куча Бродала-Окасаки]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| [[Куча Бродала-Окасаки]] (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.
|-
| [[Двоичная куча]]
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(m \log(n+m))</tex>
| [[Двоичная куча]] (англ. ''binary heap'') {{---}} такое двоичное дерево, для которого выполнены три условия:
*Значение в любой вершине не меньше, чем значения её потомков.
*Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
*Последний слой заполняется слева направо.
|-
| [[Двуродительская куча]]
| align="center" | <tex>O(\sqrt{n})</tex>
| align="center" | <tex>O(\sqrt{n})</tex>
| |
| [[Двуродительская куча]] (англ. ''bi-parental heap'' или ''beap'') {{---}} такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это не первый уровень). Структура позволяет производить сублиненый поиск.
|-
| [[d-арная куча| <tex>d</tex>-арная куча]]
| align="center" | <tex>O(\log n / \log d)</tex>
| align="center" | <tex>O(d\log n / \log d)</tex>
| align="center" | <tex>O(m \log(n+m) / \log d)</tex>
| [[d-арная куча| <tex>d</tex>-арная куча]] (англ. ''<tex>d</tex>-ary heap'') {{---}} [[двоичная куча]], в которой у каждого элемента <tex>d</tex> детей вместо <tex>2</tex>.
|-
| [[Левосторонняя куча]]
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| [[Левосторонняя куча]] (англ. ''leftist heap'') {{---}} двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи.
|-
| [[Спаренная куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| [[Спаренная куча]] (англ. ''pairing heap'') {{---}} куча с относительно простой реализацией и хорошей производительностью, может быть рассмотрена как упрощенная [[Фибоначчиева куча]].
|-
| [[Толстая куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
| [[Толстая куча]] {{---}} это почти кучеобразный нагруженный лес.
|-
| [[Тонкая куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| [[Тонкая куча]] (англ. ''thin heap'') {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
|-
| [[Фибоначчиева куча]]
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
| Куча, построенная на основе Фибоначчиева дерева. [[Фибоначчиево дерево]] (англ. ''Fibonacci tree'') {{---}} биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
|-
|}
==Применение==
* Алгоритм Дейкстры
* Алгоритм Прима
* Дискретно-событийное моделирование (англ. ''discrete-event simulation, DES'')
* Код Хаффмана
* Поиск по первому наилучшему совпадению
* Управление полосой пропускания
==Реализации в языках программирования==
* Стандартная библиотека шаблонов (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
* Библиотека Boost для C++ включает в себя библиотеку для работу с кучами. В отличии от STL, поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как [[Фибоначчиева куча]], [[Биномиальная куча]] и [[Спаренная куча]].
* В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе java.util.PriorityQueue<E>, который не поддерживает операции decrease-key и increase-key.
* Python имеет модуль heapq, который реализует очереди с приоритетами с помощью бинарной кучи.
* PHP имеет поддержку кучи на максимум (SplMaxHeap) и кучи на минимум (SplMinHeap), как часть Standard PHP Library начиная с версии 5.3.
* В Perl имеются реализации бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
* Go имеет пакет heap, в котором реализованы алгоритмы для работы с кучами.
== Источники информации ==
* [http://en.wikipedia.org/wiki/Heap_(data_structure)| Wikidedia {{---}} Heap (data structure)]
* [http://en.wikipedia.org/wiki/2%E2%80%933_heap| Wikidedia {{---}} 2-3 heap]
* [http://en.wikipedia.org/wiki/Beap| Wikidedia {{---}} Beap]
* [http://en.wikipedia.org/wiki/Binary_heap| Wikidedia {{---}} Binary heap]
* [http://en.wikipedia.org/wiki/Binomial_heap| Wikidedia {{---}} Binomial heap]
* [http://en.wikipedia.org/wiki/Brodal_queue| Wikidedia {{---}} Brodal queue]
* [http://en.wikipedia.org/wiki/D-ary_heap| Wikidedia {{---}} <tex>d</tex>-ary heap]
* [http://en.wikipedia.org/wiki/Fibonacci_heap| Wikidedia {{---}} Fibonacci heap]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
