Приоритетные очереди — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 6 участников)
Строка 1: Строка 1:
'''Приоритетная очередь''' (англ. ''priority queue'') {{---}} это абстрактная структура данных на подобии стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они распологаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью '''куч''' (англ. ''heap'').
+
'''Приоритетная очередь''' (англ. ''priority queue'') {{---}} это абстрактная структура данных наподобие стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они располагаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью '''куч''' (англ. ''heap'').
 
==Операции==
 
==Операции==
* <tex>\mathrm{findMin}</tex> или <tex>\mathrm{findMax}</tex> {{---}} поиск элемента с наибольшим приоритетом
+
Приоритетные очереди поддерживают следующие операции:
* <tex>\mathrm{insert}</tex> или <tex>\mathrm{push}</tex> {{---}} вставка нового элемента
+
* <tex>\mathrm{findMin}</tex> или <tex>\mathrm{findMax}</tex> {{---}} поиск элемента с наибольшим приоритетом,
* <tex>\mathrm{extractMin}</tex> или <tex>\mathrm{extractMax}</tex> {{---}} извлечь элемент с наибольшим приоритетом
+
* <tex>\mathrm{insert}</tex> или <tex>\mathrm{push}</tex> {{---}} вставка нового элемента,
* <tex>\mathrm{deleteMin}</tex> или <tex>\mathrm{deleteMax}</tex> {{---}} удалить элемент с наибольшим приоритетом
+
* <tex>\mathrm{extractMin}</tex> или <tex>\mathrm{extractMax}</tex> {{---}} извлечь элемент с наибольшим приоритетом,
* <tex>\mathrm{increaseKey}</tex> или <tex>\mathrm{decreaseKey}</tex> {{---}} обновить значение элемента
+
* <tex>\mathrm{deleteMin}</tex> или <tex>\mathrm{deleteMax}</tex> {{---}} удалить элемент с наибольшим приоритетом,
* <tex>\mathrm{merge}</tex> {{---}} объединение двух приоритетных очередей
+
* <tex>\mathrm{increaseKey}</tex> или <tex>\mathrm{decreaseKey}</tex> {{---}} обновить значение элемента,
* <tex>\mathrm{split}</tex> {{---}} разбить приоритную очередь на две части
+
* <tex>\mathrm{merge}</tex> {{---}} объединение двух приоритетных очередей, сохраняя оригинальные очереди,
 +
* <tex>\mathrm{meld}</tex> {{---}} объединение двух приоритетных очередей, разрушая оригинальные очереди,
 +
* <tex>\mathrm{split}</tex> {{---}} разбить приоритную очередь на две части.
 
==Реализации==
 
==Реализации==
 
===Наивная===
 
===Наивная===
Строка 13: Строка 15:
 
===Обычная===
 
===Обычная===
 
Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.
 
Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за <tex>O(\log n)</tex>. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.
==Виды приорететных очередей==
+
==Виды приоритетных очередей==
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
Строка 20: Строка 22:
 
! rowspan="2" | Описание
 
! rowspan="2" | Описание
 
|-
 
|-
| align="center" | insert
+
| align="center" | <tex>\mathrm{insert}</tex>
| align="center" width="5%" | extractMin
+
| align="center" width="5%" | <tex>\mathrm{extractMin}</tex>
| align="center" width="5%" | decreaseKey
+
| align="center" width="5%" | <tex>\mathrm{decreaseKey}</tex>
| align="center" | merge
+
| align="center" | <tex>\mathrm{merge}</tex>
 
|-
 
|-
| [[2-3 куча]]
+
| Наивная реализация (неотсортированный список)
 
| align="center" | <tex>O(1)</tex>
 
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
+
| align="center" | <tex>O(n)</tex>
 +
| align="center" | <tex>O(n)</tex>
 
| align="center" | <tex>O(1)</tex>
 
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(1)</tex>
+
| Наивная реализация с использованием списка.
| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.
 
 
|-
 
|-
| [[Тонкая куча]]
+
| Наивная реализация (отсортированный массив)
 +
| align="center" | <tex>O(n)</tex>
 
| align="center" | <tex>O(1)</tex>
 
| 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(n + m)</tex>
| align="center" | <tex>O(1)</tex>
+
| Наивная реализация с использованием отсортированного массива.
| [[Тонкая куча]] (англ. ''thin heap'') {{---}} это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.
+
|-
 +
| [[Двуродительская куча]]
 +
| align="center" | <tex>O(\sqrt{n})</tex>
 +
| align="center" | <tex>O(\sqrt{n})</tex>
 +
| |
 +
| |
 +
| [[Двуродительская куча]] (англ. ''bi-parental heap'' или ''beap'') {{---}} такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это не первый уровень). Структура позволяет производить сублиненый поиск.
 
|-
 
|-
| [[Фибоначчиева куча]]
+
| [[Двоичная куча]]
| align="center" | <tex>O(1)</tex>
+
| align="center" | <tex>O(\log n)</tex>
 +
| align="center" | <tex>O(\log n)</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(n + m)</tex>
| align="center" | <tex>O(1)</tex>
+
| [[Двоичная куча]] (англ. ''binary heap'') {{---}} такое двоичное дерево, для которого выполнены три условия:
| Куча, построенная на основе Фибоначчиева дерева. [[Фибоначчиево дерево]] (англ. ''Fibonacci tree'') {{---}} биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
+
*Значение в любой вершине не меньше, чем значения её потомков.
 +
*Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
 +
*Последний слой заполняется слева направо.
 +
|-
 +
| [[d-арная куча| <tex>d</tex>-арная куча]]
 +
| align="center" | <tex>O(\log_{d} n)</tex>
 +
| align="center" | <tex>O(d\log_{d} n)</tex>
 +
| align="center" | <tex>O(d\log_{d} n)</tex>
 +
| align="center" | <tex>O(n + m)</tex>
 +
| [[d-арная куча| <tex>d</tex>-арная куча]] (англ. ''<tex>d</tex>-ary heap'') {{---}} [[двоичная куча]], в которой у каждого элемента <tex>d</tex> детей вместо <tex>2</tex>.
 
|-
 
|-
| [[Куча Бродала-Окасаки]]
+
| [[Левосторонняя куча]]
| align="center" | <tex>O(1)</tex>
+
| align="center" | <tex>O(\log n)</tex>
 +
| align="center" | <tex>O(\log n)</tex>
 +
| align="center" | <tex>O(\log n)</tex>
 
| align="center" | <tex>O(\log n)</tex>
 
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(1)</tex>
+
| [[Левосторонняя куча]] (англ. ''leftist heap'') {{---}} двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи.
| align="center" | <tex>O(1)</tex>
 
| [[Куча Бродала-Окасаки]] (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.
 
 
|-
 
|-
 
| [[Биномиальная куча]]
 
| [[Биномиальная куча]]
| align="center" | <tex>O(1)</tex>
 
 
| align="center" | <tex>O(\log n)</tex>
 
| align="center" | <tex>O(\log n)</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(\log n)</tex>
 
| [[Биномиальная куча]] (англ. ''binomial heap'') {{---}} структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:
 
| [[Биномиальная куча]] (англ. ''binomial heap'') {{---}} структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:
 
* ключ каждой вершины не меньше ключа ее родителя  
 
* ключ каждой вершины не меньше ключа ее родителя  
Строка 76: Строка 95:
 
| [[Толстая куча]] {{---}} это почти кучеобразный нагруженный лес.
 
| [[Толстая куча]] {{---}} это почти кучеобразный нагруженный лес.
 
|-
 
|-
| [[Двоичная куча]]
+
| [[2-3 куча]]
 +
| 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(1)</tex>
 +
| Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.
 +
|-
 +
| [[Тонкая куча]]
 +
| 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(1)</tex>
 +
| [[Тонкая куча]] (англ. ''thin 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(m \log(n+m))</tex>
+
| align="center" | <tex>O(1)</tex>
| [[Двоичная куча]] (англ. ''binary heap'') {{---}} такое двоичное дерево, для которого выполнены три условия:
+
| align="center" | <tex>O(1)</tex>
*Значение в любой вершине не меньше, чем значения её потомков.
+
| Куча, построенная на основе Фибоначчиева дерева. [[Фибоначчиево дерево]] (англ. ''Fibonacci tree'') {{---}} биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
*Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
 
*Последний слой заполняется слева направо.
 
 
|-
 
|-
| [[Левосторонняя куча]]
+
| [[Куча Бродала-Окасаки]]
| align="center" | <tex>O(\log n)</tex>
+
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(\log n)</tex>
 
 
| align="center" | <tex>O(\log n)</tex>
 
| align="center" | <tex>O(\log n)</tex>
| align="center" | <tex>O(\log n)</tex>
 
| [[Левосторонняя куча]] (англ. ''leftist heap'') {{---}} двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи.
 
|-
 
| [[d-арная куча| <tex>d</tex>-арная куча]]
 
| align="center" | <tex>O(\log_{d} n)</tex>
 
| align="center" | <tex>O(d\log_{d} n)</tex>
 
| align="center" | <tex>O(\log_{d} n)</tex>
 
| align="center" | <tex>O(m \log_{d}(n+m))</tex>
 
| [[d-арная куча| <tex>d</tex>-арная куча]] (англ. ''<tex>d</tex>-ary heap'') {{---}} [[двоичная куча]], в которой у каждого элемента <tex>d</tex> детей вместо <tex>2</tex>.
 
|-
 
| [[Двуродительская куча]]
 
| align="center" | <tex>O(\sqrt{n})</tex>
 
| align="center" | <tex>O(\sqrt{n})</tex>
 
| |
 
| |
 
| [[Двуродительская куча]] (англ. ''bi-parental heap'' или ''beap'') {{---}} такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это не первый уровень). Структура позволяет производить сублиненый поиск.
 
|-
 
| Наивная реализация
 
 
| align="center" | <tex>O(1)</tex>
 
| align="center" | <tex>O(1)</tex>
| align="center" | <tex>O(n)</tex>
 
| align="center" | <tex>O(n)</tex>
 
 
| align="center" | <tex>O(1)</tex>
 
| align="center" | <tex>O(1)</tex>
| Наивная реализация с использованием списка.
+
| [[Куча Бродала-Окасаки]] (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.
 
|-
 
|-
 
|}
 
|}
 +
 
==Применение==
 
==Применение==
Приоритетные очереди используются в следующих алгоритмах: [[алгоритм Дейкстры]], [[алгоритм Прима]], дискретно-событийное моделирование (англ. ''discrete-event simulation, DES''), [[алгоритм Хаффмана]], поиск по первому наилучшему совпадению, управление полосой пропускания.
+
Приоритетные очереди используются в следующих алгоритмах: [[алгоритм Дейкстры]], [[алгоритм Прима]], дискретно-событийное моделирование (англ. ''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>, [[алгоритм Хаффмана]], поиск по первому наилучшему совпадению, управление полосой пропускания.
 
==Реализации в языках программирования==
 
==Реализации в языках программирования==
* [http://en.cppreference.com/w/cpp/container Стандартная библиотека шаблонов] (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
+
* Стандартная библиотека шаблонов<ref>[http://en.cppreference.com/w/cpp/container C++ {{---}} Стандартная библиотека шаблонов]</ref> (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
* Библиотека [http://www.boost.org/ Boost] для C++ включает в себя библиотеку для работу с кучами. В отличии от [http://en.cppreference.com/w/cpp/container STL], поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как [[фибоначчиева куча]], [[биномиальная куча]] и [[спаренная куча]].
+
* Библиотека Boost<ref>[http://www.boost.org/ C++ {{---}} Boost]</ref> для C++ включает в себя библиотеку для работу с кучами. В отличии от STL, поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как [[фибоначчиева куча]], [[биномиальная куча]] и [[спаренная куча]].
* В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе [http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html java.util.PriorityQueue<E>], который не поддерживает операции decrease-key и increase-key.
+
* В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе java.util.PriorityQueue<E><ref>[http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html Java {{---}} java.util.PriorityQueue<E>]</ref>, который не поддерживает операции decrease-key и increase-key.
* Python имеет модуль [http://docs.python.org/2/library/heapq.html heapq], который реализует очереди с приоритетами с помощью бинарной кучи.
+
* Python имеет модуль heapq<ref>[http://docs.python.org/2/library/heapq.html Python {{---}} heapq]</ref>, который реализует очереди с приоритетами с помощью бинарной кучи.
* PHP имеет поддержку кучи на максимум [http://php.net/manual/ru/class.splmaxheap.php SplMaxHeap] и кучи на минимум [http://php.net/manual/ru/class.splminheap.php SplMinHeap], как часть Standard PHP Library начиная с версии 5.3.
+
* PHP имеет поддержку кучи на максимум SplMaxHeap<ref>[http://php.net/manual/ru/class.splmaxheap.php PHP {{---}} SplMaxHeap]</ref> и кучи на минимум SplMinHeap<ref>[http://php.net/manual/ru/class.splminheap.php PHP {{---}} SplMinHeap]</ref>, как часть Standard PHP Library начиная с версии 5.3.
* В Perl имеются [http://metacpan.org/pod/Heap реализации] бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
+
* В Perl имеются реализации<ref>[http://metacpan.org/pod/Heap Perl {{---}} Heap]</ref> бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
* Go имеет пакет [http://golang.org/pkg/container/heap/ heap], в котором реализованы алгоритмы для работы с кучами.
+
* Go имеет пакет heap<ref>[http://golang.org/pkg/container/heap/ Go {{---}} package heap]</ref>, в котором реализованы алгоритмы для работы с кучами.
 
==См. также==
 
==См. также==
 
*[[:Сортировка|Сортировка]]
 
*[[:Сортировка|Сортировка]]
 
*[[:Поисковые структуры данных|Поисковые структуры данных]]
 
*[[:Поисковые структуры данных|Поисковые структуры данных]]
 +
*[[:Поиск подстроки в строке|Поиск подстроки в строке]]
 +
==Примечания==
 +
 +
<references />
 
== Источники информации ==
 
== Источники информации ==
* [http://en.wikipedia.org/wiki/Heap_(data_structure) Wikidedia {{---}} Heap (data structure)]
+
* [http://en.wikipedia.org/wiki/Heap_(data_structure) Wikipedia {{---}} Heap (data structure)]
* [http://en.wikipedia.org/wiki/2%E2%80%933_heap Wikidedia {{---}} 2-3 heap]
+
* [http://en.wikipedia.org/wiki/2%E2%80%933_heap Wikipedia {{---}} 2-3 heap]
* [http://en.wikipedia.org/wiki/Beap Wikidedia {{---}} Beap]
+
* [http://en.wikipedia.org/wiki/Beap Wikipedia {{---}} Beap]
* [http://en.wikipedia.org/wiki/Binary_heap Wikidedia {{---}} Binary heap]
+
* [http://en.wikipedia.org/wiki/Binary_heap Wikipedia {{---}} Binary heap]
* [http://en.wikipedia.org/wiki/Binomial_heap Wikidedia {{---}} Binomial heap]
+
* [http://en.wikipedia.org/wiki/Binomial_heap Wikipedia {{---}} Binomial heap]
* [http://en.wikipedia.org/wiki/Brodal_queue Wikidedia {{---}} Brodal queue]
+
* [http://en.wikipedia.org/wiki/Brodal_queue Wikipedia {{---}} Brodal queue]
* [http://en.wikipedia.org/wiki/D-ary_heap Wikidedia {{---}} <tex>d</tex>-ary heap]
+
* [http://en.wikipedia.org/wiki/D-ary_heap Wikipedia {{---}} <tex>d</tex>-ary heap]
* [http://en.wikipedia.org/wiki/Fibonacci_heap Wikidedia {{---}} Fibonacci heap]
+
* [http://en.wikipedia.org/wiki/Fibonacci_heap Wikipedia {{---}} Fibonacci heap]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Структуры данных]]
 
[[Категория: Структуры данных]]

Текущая версия на 19:07, 4 сентября 2022

Приоритетная очередь (англ. priority queue) — это абстрактная структура данных наподобие стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они располагаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью куч (англ. heap).

Операции

Приоритетные очереди поддерживают следующие операции:

  • [math]\mathrm{findMin}[/math] или [math]\mathrm{findMax}[/math] — поиск элемента с наибольшим приоритетом,
  • [math]\mathrm{insert}[/math] или [math]\mathrm{push}[/math] — вставка нового элемента,
  • [math]\mathrm{extractMin}[/math] или [math]\mathrm{extractMax}[/math] — извлечь элемент с наибольшим приоритетом,
  • [math]\mathrm{deleteMin}[/math] или [math]\mathrm{deleteMax}[/math] — удалить элемент с наибольшим приоритетом,
  • [math]\mathrm{increaseKey}[/math] или [math]\mathrm{decreaseKey}[/math] — обновить значение элемента,
  • [math]\mathrm{merge}[/math] — объединение двух приоритетных очередей, сохраняя оригинальные очереди,
  • [math]\mathrm{meld}[/math] — объединение двух приоритетных очередей, разрушая оригинальные очереди,
  • [math]\mathrm{split}[/math] — разбить приоритную очередь на две части.

Реализации

Наивная

В качестве наивной реализации мы можем взять обычный список и при добавлении нового элемента класть его в конец, а при запросе элемента с максимальным приоритетом проходить по всему списку. Тогда операция [math]\mathrm{insert}[/math] будет выполняться за [math]O(1)[/math], а [math]\mathrm{extractMin}[/math] или [math]\mathrm{extractMax}[/math] за [math]O(n)[/math].

Обычная

Для лучшей производительности приоритетные очереди реализуют с помощью куч, что позволяет выполнять операции вставки и удаления за [math]O(\log n)[/math]. Использование специальных куч, таких как Фибоначчиева куча и спаренная куча, позволяет еще больше улучшить асимптотику некоторый операций.

Виды приоритетных очередей

Название Операции Описание
[math]\mathrm{insert}[/math] [math]\mathrm{extractMin}[/math] [math]\mathrm{decreaseKey}[/math] [math]\mathrm{merge}[/math]
Наивная реализация (неотсортированный список) [math]O(1)[/math] [math]O(n)[/math] [math]O(n)[/math] [math]O(1)[/math] Наивная реализация с использованием списка.
Наивная реализация (отсортированный массив) [math]O(n)[/math] [math]O(1)[/math] [math]O(\log n)[/math] [math]O(n + m)[/math] Наивная реализация с использованием отсортированного массива.
Двуродительская куча [math]O(\sqrt{n})[/math] [math]O(\sqrt{n})[/math] Двуродительская куча (англ. bi-parental heap или beap) — такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это не первый уровень). Структура позволяет производить сублиненый поиск.
Двоичная куча [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(n + m)[/math] Двоичная куча (англ. binary heap) — такое двоичное дерево, для которого выполнены три условия:
  • Значение в любой вершине не меньше, чем значения её потомков.
  • Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
  • Последний слой заполняется слева направо.
[math]d[/math]-арная куча [math]O(\log_{d} n)[/math] [math]O(d\log_{d} n)[/math] [math]O(d\log_{d} n)[/math] [math]O(n + m)[/math] [math]d[/math]-арная куча (англ. [math]d[/math]-ary heap) — двоичная куча, в которой у каждого элемента [math]d[/math] детей вместо [math]2[/math].
Левосторонняя куча [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] Левосторонняя куча (англ. leftist heap) — двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи.
Биномиальная куча [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] Биномиальная куча (англ. binomial heap) — структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:
  • ключ каждой вершины не меньше ключа ее родителя
  • все биномиальные деревья имеют разный размер
Спаренная куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(1)[/math] Спаренная куча (англ. pairing heap) — куча с относительно простой реализацией и хорошей производительностью, может быть рассмотрена как упрощенная Фибоначчиева куча.
Толстая куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] [math]O(\log n)[/math] Толстая куча — это почти кучеобразный нагруженный лес.
2-3 куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] [math]O(1)[/math] Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.
Тонкая куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] [math]O(1)[/math] Тонкая куча (англ. thin heap) — это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и фибоначчиева куча, но имеющая большую практическую ценность из-за меньших констант.
Сонная куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] [math]O(1)[/math] Куча, построенная на основе Фибоначчиева дерева. Фибоначчиево дерево (англ. Fibonacci tree) — биномиальное дерево, где у каждой вершины удалено не более одного ребенка.
Куча Бродала-Окасаки [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] [math]O(1)[/math] Куча Бродала-Окасаки (англ. Brodal's and Okasaki's Priority Queue) — основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.

Применение

Приоритетные очереди используются в следующих алгоритмах: алгоритм Дейкстры, алгоритм Прима, дискретно-событийное моделирование (англ. discrete-event simulation, DES)[1], алгоритм Хаффмана, поиск по первому наилучшему совпадению, управление полосой пропускания.

Реализации в языках программирования

  • Стандартная библиотека шаблонов[2] (англ. STL) в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
  • Библиотека Boost[3] для C++ включает в себя библиотеку для работу с кучами. В отличии от STL, поддерживает операции decrease-key и increase-key, а также имеет поддержку дополнительных видов куч, таких как фибоначчиева куча, биномиальная куча и спаренная куча.
  • В Java 2 (начиная с версии 1.5) предоставляется реализация бинарной кучи в классе java.util.PriorityQueue<E>[4], который не поддерживает операции decrease-key и increase-key.
  • Python имеет модуль heapq[5], который реализует очереди с приоритетами с помощью бинарной кучи.
  • PHP имеет поддержку кучи на максимум SplMaxHeap[6] и кучи на минимум SplMinHeap[7], как часть Standard PHP Library начиная с версии 5.3.
  • В Perl имеются реализации[8] бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
  • Go имеет пакет heap[9], в котором реализованы алгоритмы для работы с кучами.

См. также

Примечания

Источники информации