Войти
При разработке и анализе структур данных, bucket queue (также называемая очередь приоритетов корзины или очередь приоритетов с ограниченной высотой ) - это очередь приоритетов для приоритезации элементов, приоритеты которых являются небольшими целыми числами. Он имеет форму массива сегментов: структура данных массива, индексированная по приоритетам, ячейки которой содержат сегменты элементов с одинаковым приоритетом.
Очередь корзин является аналогом очереди с приоритетом сортировки по ячейкам (также называемой сортировкой по сегментам), алгоритма сортировки, который помещает элементы в сегменты, индексированные по их приоритетам, а затем объединяет сегменты. Использование очереди ведра в качестве очереди с приоритетом в сортировке выбора дает форму алгоритма сортировки по ячейкам.
Применения очереди ведра включают вычисление вырожденности графа, а также быстрые алгоритмы для кратчайших путей и самых широких пути для графиков с небольшими целыми числами или весами, которые уже отсортированы. Его первое использование было в алгоритме кратчайшего пути Dial (1969).
Эта структура может обрабатывать вставки и удаления элементов с целочисленными приоритетами в диапазоне от 0 до некоторой известной границы C, а также операции, которые находят элемент с минимальным (или максимальным) приоритетом. Он состоит из массива A контейнерных структур данных, где в ячейке массива A [p] хранится коллекция элементов с приоритетом p. Он может обрабатывать следующие операции:
Таким образом, вставки и удаления занимают постоянное время, в то время как поиск элемента с минимальным приоритетом занимает время O (C).
В качестве оптимизации структура данных также может поддерживать индекс L, который ограничивает минимальный приоритет элемента. При вставке нового элемента L должен быть обновлен до минимума из своего старого значения и приоритета нового элемента. При поиске элемента с минимальным приоритетом поиск может начинаться с L вместо нуля, и после поиска L следует оставить равным приоритету, который был найден при поиске. Таким образом, время поиска сокращается до разницы между предыдущей нижней границей и ее следующим значением; эта разница может быть значительно меньше, чем C. Для приложений с очередями с монотонным приоритетом, такими как алгоритм Дейкстры, в котором минимальные приоритеты образуют монотонную последовательность, сумма эти различия не превышают C, поэтому общее время для последовательности из n операций составляет O (n + C), а не более медленное ограничение по времени O (nC), которое было бы без этой оптимизации.
Другая оптимизация (уже заданная Dial 1969) может использоваться для экономии места, когда приоритеты монотонны и в любой момент времени попадают в диапазон значений r, а не расширяются во всем диапазоне от 0 до C. В этом случае можно индексировать массив по приоритетам по модулю r, а не по их фактическим значениям. Поиск элемента с минимальным приоритетом всегда должен начинаться с предыдущего минимума, чтобы избежать приоритетов, которые выше минимального, но имеют более низкие модули.
Для поддержки вершин неориентированного графа , с приоритетом их степеней, и многократно находят и удаляют вершину минимальной степени. Этот жадный алгоритм можно использовать для вычисления вырожденности данного графа. Требуется линейное время с оптимизацией или без нее, которая поддерживает нижнюю границу минимального приоритета, потому что каждая вершина находится во времени, пропорциональном ее степени, а сумма всех степеней вершин линейна по количеству ребер графа.
В алгоритме Дейкстры для кратчайших путей в положительно-взвешенных ориентированных графах можно использовать очередь ведра для получения временная граница O (n + m + dc), где n - количество вершин, m - количество ребер, d - диаметр сети, а c - максимальная (целочисленная) стоимость ссылки. Этот вариант алгоритма Дейкстры также известен как алгоритм Диала в честь Роберта Б. Диала, который опубликовал его в 1969 году. В этом алгоритме приоритеты будут охватывать только диапазон ширины c + 1, поэтому модульный можно использовать оптимизацию, чтобы уменьшить пространство до O (n + c). Вариант того же алгоритма может использоваться для задачи с самым широким путем, и (в сочетании с методами быстрого разделения нецелочисленных весов ребер) приводит к решениям с одним источником единственного -пункт назначения этой проблемы.
