Очередь ведра - Bucket queue - Wikipedia

При проектировании и анализе структуры данных, а очередь ведра[1] (также называемый очередь с приоритетом ведра[2] или же приоритетная очередь с ограниченной высотой[3]) это приоритетная очередь для определения приоритетов элементов, чьи приоритеты небольшие целые числа. Он имеет форму массива ведер: структура данных массива, индексируемые по приоритетам, ячейки которых содержат ведра элементов с одинаковым приоритетом.

Bucket queue является аналогом очереди с приоритетом голубятня сортировка (также называемый сортировкой по сегментам), алгоритм сортировки, который помещает элементы в сегменты, индексированные по их приоритетам, а затем объединяет сегменты. Использование очереди сегментов в качестве очереди с приоритетом в сортировка выбора дает форму алгоритма сортировки по ячейкам.

Применения очереди ведра включают вычисление вырождение графа а также быстро алгоритмы за кратчайшие пути и широчайшие пути для графов с небольшими целыми числами или уже отсортированными весами. Его первое использование[2] был в алгоритме кратчайшего пути Циферблат (1969).[4]

Базовая структура данных

Эта структура может обрабатывать вставки и удаления элементов с целочисленными приоритетами в диапазоне от 0 до некоторой известной границы. C, а также операции, которые находят элемент с минимальным (или максимальным) приоритетом. Он состоит из массива А из структуры данных контейнера, где ячейка массива А[п] хранит коллекцию элементов с приоритетом п.Он может выполнять следующие операции:

  • Чтобы вставить элемент Икс с приоритетом п, Добавить Икс в контейнер на А[п].
  • Чтобы удалить элемент Икс с приоритетом п, удалять Икс из контейнера в А[п]
  • Чтобы найти элемент с минимальным приоритетом, выполните последовательный поиск чтобы найти первый непустой контейнер, а затем выбрать произвольный элемент из этого контейнера.

Таким образом, вставки и удаления занимают постоянное время, а поиск элемента с минимальным приоритетом требует времени. О(C).[1][3]

Оптимизация

В качестве оптимизации структура данных также может поддерживать индекс L который нижняя граница минимальный приоритет элемента. При вставке нового элемента L должен быть обновлен до минимума старого значения и приоритета нового элемента. При поиске элемента с минимальным приоритетом поиск может начинаться с L вместо нуля, а после поиска L следует оставить равным приоритету, найденному при поиске.[3] Таким образом, время поиска сокращается до разницы между предыдущей нижней границей и ее следующим значением; эта разница может быть значительно меньше, чем C. Для приложений очереди с монотонным приоритетом Такие как Алгоритм Дейкстры в котором минимальные приоритеты образуют монотонная последовательность, сумма этих разностей не более C, поэтому общее время для последовательности п операции О(п + C), а не более медленный О(nC) ограничение по времени, которое получилось бы без этой оптимизации.

Другая оптимизация (уже предоставленная Набери 1969 ) можно использовать для экономии места, когда приоритеты монотонны и в любой момент времени попадают в диапазон р значений вместо того, чтобы распространяться на весь диапазон от 0 до C. В этом случае можно индексировать массив по приоритетам по модулю р а не их фактическими значениями. Поиск элемента с минимальным приоритетом всегда должен начинаться с предыдущего минимума, чтобы избежать приоритетов, которые выше минимума, но имеют более низкие модули.[1]

Приложения

Очередь ведра может использоваться для поддержания вершины из неориентированный граф, в первую очередь градусы, и несколько раз найти и удалить вершину минимальной степени.[3] Этот жадный алгоритм можно использовать для расчета вырождение данного графа. Занимает линейное время, с оптимизацией или без нее, которая поддерживает нижнюю границу минимального приоритета, потому что каждая вершина находится во времени, пропорциональном ее степени, а сумма всех степеней вершин линейна по количеству ребер графа.[5]

В Алгоритм Дейкстры за кратчайшие пути в положительно взвешенных ориентированные графы, очередь ведра может использоваться, чтобы получить временную границу О(п + м + Округ Колумбия), куда п - количество вершин, м это количество ребер, d диаметр сети, а c - максимальная (целая) стоимость ссылки.[6] Этот вариант алгоритма Дейкстры также известен как Алгоритм набора после Роберта Б. Диала, опубликовавшего его в 1969 году.[4] В этом алгоритме приоритеты будут охватывать только диапазон ширины c + 1, поэтому модульную оптимизацию можно использовать для уменьшения пространства до О(п + c).[1]Вариант того же алгоритма можно использовать для проблема самого широкого пути, и (в сочетании с методами быстрого разделения нецелочисленных весов ребер) приводит к почти линейным временным решениям для версии этой проблемы с одним источником и одним адресатом.[7]

Рекомендации

  1. ^ а б c d Мельхорн, Курт; Сандерс, Питер (2008), «10.5.1 Bucket Queues», Алгоритмы и структуры данных: базовый набор инструментов, Springer, стр. 201, ISBN  9783540779773.
  2. ^ а б Эделькамп, Стефан; Шредль, Стефан (2011), «3.1.1 Структуры данных корзины», Эвристический поиск: теория и приложения, Elsevier, стр. 90–92, ISBN  9780080919737. Также стр. 157 для истории и наименования этой структуры.
  3. ^ а б c d Скиена, Стивен С. (1998), Руководство по разработке алгоритмов, Springer, стр. 181, ISBN  9780387948607.
  4. ^ а б Диал, Роберт Б. (1969), «Алгоритм 360: лес кратчайшего пути с топологическим упорядочением [H]», Коммуникации ACM, 12 (11): 632–633, Дои:10.1145/363269.363610.
  5. ^ Матула, Дэвид В .; Бек, Л. Л. (1983), "Алгоритмы наименьшего последнего упорядочения, кластеризации и раскраски графов", Журнал ACM, 30 (3): 417–427, Дои:10.1145/2402.322385, МИСТЕР  0709826.
  6. ^ Варгезе, Джордж (2005), Сетевая алгоритмика: междисциплинарный подход к разработке быстрых сетевых устройств, Морган Кауфманн, ISBN  9780120884773.
  7. ^ Габоу, Гарольд Н .; Тарджан, Роберт Э. (1988), «Алгоритмы для двух задач оптимизации узких мест», Журнал алгоритмов, 9 (3): 411–417, Дои:10.1016/0196-6774(88)90031-4, МИСТЕР  0955149