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

Материал из Викиконспекты
Версия от 21:42, 6 июня 2015; Eadm (обсуждение | вклад) (Отмена правки 47848 участника, ошибка)
Перейти к: навигация, поиск

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

Операции

  • find-min (find-max) - поиск элемента с наибольшим приоритетом
  • insert (push) - вставка нового элемента
  • extract-min (extract-max) - извлечь элемент с наибольшим приоритетом
  • delete-min (delete-max) - удалить элемент с наибольшим приоритетом
  • merge - объединение двух приоритетных очередей

Реализации

Наивная

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

Обычная

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

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

Название Операции Описание
find-min insert delete-min merge
2-3 куча [math]O(1)[/math] [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] Структура похожа на Фибоначчиеву кучу и использует в своей реализации 2-3 дерево.
Биномиальная куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] Биномиальная куча (англ. binomial heap) — структура данных, реализующая приоритетную очередь, которая представляет собой набор биномиальных деревьев с двумя свойствами:
  • ключ каждой вершины не меньше ключа ее родителя
  • все биномиальные деревья имеют разный размер
Куча Бродала-Окасаки [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] Куча Бродала-Окасаки (англ. Brodal's and Okasaki's Priority Queue) — основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping.
Двоичная куча [math]O(\log n)[/math] [math]O(\log n)[/math] [math]O(m \log(n+m))[/math] Двоичная куча (англ. binary heap) — такое двоичное дерево, для которого выполнены три условия:
  • Значение в любой вершине не меньше, чем значения её потомков.
  • Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
  • Последний слой заполняется слева направо.
Двуродительская куча [math]O(\sqrt{n})[/math] [math]O(\sqrt{n})[/math] Двуродительская куча (англ. bi-parental heap или beap) — такая куча, где у каждого элемента обычно есть два ребенка (если это не последний уровень) и два родителя (если это не первый уровень). Структура позволяет производить сублиненый поиск.
[math]d[/math]-арная куча [math]O(\log n / \log d)[/math] [math]O(d\log n / \log d)[/math] [math]O(m \log(n+m) / \log d)[/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] Левосторонняя куча (англ. leftist heap) — двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи.
Спаренная куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] Спаренная куча (англ. pairing heap) — куча с относительно простой реализацией и хорошей производительностью, может быть рассмотрена как упрощенная Фибоначчиева куча.
Толстая куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(\log n)[/math] Толстая куча — это почти кучеобразный нагруженный лес.
Тонкая куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] Тонкая куча (англ. thin heap) — это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и фибоначчиева куча, но имеющая большую практическую ценность из-за меньших констант.
Фибоначчиева куча [math]O(1)[/math] [math]O(\log n)[/math] [math]O(1)[/math] Куча, построенная на основе Фибоначчиева дерева. Фибоначчиево дерево (англ. 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://neerc.ifmo.ru/wiki/index.php?title=Поисковые_структуры_данных&oldid=47849»