Изменения

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

Поисковые структуры данных

11 байт добавлено, 21:42, 6 июня 2015
Отмена правки 47848 участника, ошибка
'''Приоритетная очередь''' (англ. ''priority queue'') {{---}} это абстрактная структура данных на подобии стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они распологаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью куч (англ. ''heap'').
 
==Операции==
 
* find-min (find-max) - поиск элемента с наибольшим приоритетом
* insert (push) - вставка нового элемента
* 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"
|-
|-
|}
 
==Применение==
* Алгоритм Дейкстры
* Поиск по первому наилучшему совпадению
* Управление полосой пропускания
 
==Реализации в языках программирования==
* Стандартная библиотека шаблонов (англ. ''STL'') в C++ предоставляет методы управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного случайного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
* В Perl имеются реализации бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.
* Go имеет пакет heap, в котором реализованы алгоритмы для работы с кучами.
 
 
 
== Источники информации ==
* [http://en.wikipedia.org/wiki/Heap_(data_structure)| Wikidedia {{---}} Heap (data structure)]
48
правок

Навигация