Bucket queue - Википедия - Bucket queue

При проектировании и анализе структуры данных, а очередь ведра^[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]

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