Очередь сегментов

Очередь сегментов
Очередь сегментов
	Массив сегментов, подходящий для приоритетов в диапазоне от 1 до 6. Элемент с минимальным приоритетом можно найти в крайнем левом непустом сегменте.
Тип	приоритетная очередь
Изобретенный	1969
Изобретён	Роберт Дайал
Операция
Временная сложность в обозначении большого О
Операция	Средний
Вставлять	О (1)
Найти-мин	О (#приоритеты)
Удалить-мин.	О (#приоритеты)
Клавиша уменьшения	О (1)
Пространственная сложность

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

Очередь сегментов — это аналог сортировки по ячейкам (также называемой сортировкой сегментов) с приоритетной очередью. Это алгоритм сортировки, который помещает элементы в сегменты, индексированные по их приоритетам, а затем объединяет сегменты. Использование очереди сегментов в качестве приоритетной очереди при сортировке выбором дает форму алгоритма сортировки по ячейкам. ^[2] Очереди сегментов также называются очередями приоритетов сегментов. ^[3] или очереди с приоритетом ограниченной высоты . ^[1] Когда они используются для квантованного приближения к приоритетам действительных чисел , их также называют неопрятными очередями приоритетов. ^[4] или очереди с псевдоприоритетом . ^[5] Они тесно связаны с календарной очередью — структурой, которая использует аналогичный массив сегментов для точной расстановки приоритетов по действительным числам.

Приложения очереди сегментов включают вычисление вырождения графа , быстрые алгоритмы для поиска кратчайших путей и широчайших путей для графов с весами, которые являются небольшими целыми числами или уже отсортированы, а также алгоритмы жадной аппроксимации для задачи покрытия множеств . Квантованная версия структуры также применялась для планирования. ^[2] и марширующим кубикам в компьютерной графике . ^[4] Первое использование очереди сегментов ^[6] был в алгоритме кратчайшего пути Дайала (1969) . ^[7]

Операция

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

Очередь сегментов может обрабатывать элементы с целочисленными приоритетами в диапазоне от 0 или 1 до некоторой известной границы $C$ , а также операции, которые вставляют элементы, изменяют приоритет элементов или извлекают (находят и удаляют) элемент, который имеет минимальное (или максимальный) приоритет. Он состоит из массива $A$ структур данных-контейнеров ; в большинстве источников эти контейнеры представляют собой двусвязные списки, но в качестве альтернативы они могут быть динамическими массивами. ^[3] или динамические наборы . Контейнер в $ячейке p$ -го массива $A [p]$ хранит коллекцию элементов, приоритет которых равен $p$ .

Очередь сегментов может обрабатывать следующие операции:

Чтобы вставить элемент $x$ с приоритетом $p$ , добавьте $x$ в контейнер по адресу $A [p]$ .
Чтобы изменить приоритет элемента, удалите его из контейнера со старым приоритетом и повторно вставьте в контейнер с новым приоритетом.
Чтобы извлечь элемент с минимальным или максимальным приоритетом, выполните последовательный поиск в массиве, чтобы найти первый или последний непустой контейнер, соответственно, выберите произвольный элемент из этого контейнера и удалите его из контейнера.

Таким образом, вставки и изменения приоритета занимают постоянное время, а извлечение элемента с минимальным или максимальным приоритетом занимает время $O (C)$ . ^[1]^[6]^[8]

Оптимизации

В качестве оптимизации структура данных может начинать каждый последовательный поиск непустой корзины с последней найденной непустой корзины, а не с начала массива. Это можно сделать двумя способами: ленивым (откладывая последовательные поиски до тех пор, пока они не потребуются) или активным (выполняя поиск заранее). Выбор того, когда выполнять поиск, влияет на то, какие операции со структурами данных замедляются в результате этих поисков. В исходной версии структуры Dial использовался отложенный поиск. Это можно сделать, поддерживая индекс $L$ , который является нижней границей минимального приоритета любого элемента, находящегося в данный момент в очереди. При вставке нового элемента $L$ должен быть обновлен до минимума его старого значения и приоритета нового элемента. При поиске элемента с минимальным приоритетом поиск можно начинать с $L,$ а не с нуля, а после поиска $L$ следует оставить равным приоритету, который был найден при поиске. ^[7]^[9] Альтернативно, энергичная версия этой оптимизации поддерживает $обновление L$ , чтобы оно всегда указывало на первую непустую корзину. При вставке нового элемента с приоритетом меньшим, чем $L$ , структура данных устанавливает $L$ новый приоритет, а при удалении последнего элемента из корзины с приоритетом $L$ она выполняет последовательный поиск по более крупным индексам, пока не найдет непустую корзину. и установка $L$ в качестве приоритета результирующего сегмента. ^[1]

пропорциональное разнице между старым и новым значениями $L.$ В любом из этих двух вариантов каждый последовательный поиск занимает время , Это может быть значительно быстрее, чем $время O (C)$ для поиска в неоптимизированной версии структуры данных. Во многих приложениях очередей с приоритетами, таких как алгоритм Дейкстры , минимальные приоритеты образуют монотонную последовательность , что позволяет монотонную очередь с приоритетами использовать . В этих приложениях, как для ленивых, так и для энергичных вариантов оптимизированной структуры, последовательный поиск непустых сегментов охватывает непересекающиеся диапазоны сегментов. Поскольку каждый сегмент находится не более чем в одном из этих диапазонов, их количество шагов в сумме составляет не более $C$ . Следовательно, в этих приложениях общее время для последовательности из $n$ операций равно $O (n + C)$ , а не более медленному $ограничению времени O (nC),$ которое могло бы возникнуть без этой оптимизации. ^[9] Соответствующая оптимизация может быть применена в приложениях, где очередь сегментов используется для поиска элементов с максимальным приоритетом, но в этом случае она должна поддерживать индекс, ограничивающий верхний предел максимального приоритета, и должен продолжаться последовательный поиск непустой корзины. вниз от этой верхней границы. ^[10]

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

Поскольку создание новой очереди сегментов включает в себя инициализацию массива пустых сегментов, этот шаг инициализации занимает время, пропорциональное количеству приоритетов. Вариант очереди корзин, описанный Дональдом Б. Джонсоном в 1981 году, вместо этого хранит только непустые корзины в связанном списке, отсортированные по их приоритетам, и использует вспомогательное дерево поиска, чтобы быстро найти позицию в этом связанном списке для любого нового ведра. Требуется время $O (log log C)$ для инициализации этой вариантной структуры, постоянное время для поиска элемента с минимальным или максимальным приоритетом и время $O (log log D)$ для вставки или удаления элемента, где $D$ — разница между ближайшими меньшие и большие приоритеты относительно приоритета вставленного или удаленного элемента. ^[11]

Пример

Например, рассмотрим очередь сегментов с четырьмя приоритетами: числами 0, 1, 2 и 3. Она состоит из массива $A$ каждая из четырех ячеек которого содержит набор элементов, изначально пустых. Для целей этого примера $A$ можно записать в виде последовательности из четырех наборов в квадратных скобках: $A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]$ . Рассмотрим последовательность операций, в которую мы вставляем два элемента $x$ и $y$ с тем же приоритетом 1 вставьте третий элемент $z$ с приоритетом 3, измените приоритет $x$ до 3, а затем выполнить два извлечения элемента с минимальным приоритетом.

После вставки $x$ с приоритетом 1, $A=[\emptyset ,\{x\},\emptyset ,\emptyset ]$ .
После вставки $y$ с приоритетом 1, $A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]$ .
После вставки z с приоритетом 3, $A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]$ .
Изменение приоритета x с 1 на три предполагает его удаление из $A[1]$ и добавив его в $A[3]$ , после чего $A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]$ .
Извлечение элемента с минимальным приоритетом в базовой версии очереди сегментов осуществляет поиск с начала $A$ чтобы найти его первый непустой элемент: $A[0]$ пусто, но $A[1]=\{y\}$ , непустое множество. Он выбирает произвольный элемент этого множества (единственный элемент, $y$ ) как элемент с минимальным приоритетом. Удаление $y$ из структуры уходит $A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]$ .
Вторая операция извлечения в базовой версии очереди сегментов снова выполняет поиск с начала массива: $A[0]=\emptyset$ , $A[1]=\emptyset$ , $A[2]=\emptyset$ , $A[3]={}$ непустой. В улучшенных вариантах очереди сегментов этот поиск начинается с последней позиции, которая оказалась непустой. $A[1]$ . В любом случае, $A[3]=\{x,z\}$ оказывается первым непустым множеством. Один из его элементов выбирается произвольно как элемент с минимальным приоритетом; например, $z$ может быть выбран. Этот элемент удаляется, оставляя $A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]$ .

Приложения

Вырождение графа

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

Алгоритм Дайала для поиска кратчайших путей

В алгоритме Дейкстры для поиска кратчайших путей в ориентированных графах с весами ребер, которые являются положительными целыми числами, приоритеты монотонны, ^[13] и монотонную очередь сегментов можно использовать для получения временной границы $O (m + dc)$ , где $m$ — количество ребер, $d$ — диаметр сети, а $c$ — максимальная (целая) стоимость канала. ^[9]^[14] Этот вариант алгоритма Дейкстры также известен как алгоритм Дайала . ^[9] после Роберта Б. Дайала, опубликовавшего его в 1969 году. ^[7] Та же идея также работает с использованием квантовой очереди сегментов для графов с положительными действительными весами ребер, когда отношение максимального к минимальному весу не превышает $c$ . ^[15] В этой квантованной версии алгоритма вершины обрабатываются не по порядку, по сравнению с результатом с неквантованной приоритетной очередью, но правильные кратчайшие пути все равно находятся. ^[5] В этих алгоритмах приоритеты будут охватывать только диапазон ширины $c + 1$ , поэтому модульную оптимизацию можно использовать для уменьшения пространства до $O (n + c)$ . ^[8]^[14]

Вариант того же алгоритма можно использовать для решения задачи о самом широком пути . В сочетании с методами быстрого разделения нецелочисленных весов ребер на подмножества, которым могут быть назначены целочисленные приоритеты, это приводит к почти линейному времени решения версии проблемы наибольшего пути с одним источником и одним пунктом назначения. ^[16]

Обложка набора «Жадный»

Задача о покрытии множеств имеет на входе семейство множеств . Выходные данные должны представлять собой подсемейство этих наборов с тем же объединением, что и исходное семейство, включая как можно меньше наборов. Это NP-трудный метод , но он имеет жадный алгоритм аппроксимации , который обеспечивает логарифмический коэффициент аппроксимации, по сути, наилучший из возможных, если только P = NP . ^[17] Этот алгоритм аппроксимации выбирает свое подсемейство путем многократного выбора набора, который покрывает максимально возможное количество оставшихся непокрытых элементов. ^[18] Стандартное упражнение по разработке алгоритма требует реализации этого алгоритма, которая требует линейного времени в зависимости от размера входных данных, который представляет собой сумму размеров всех входных наборов. ^[19]

Эту проблему можно решить, используя очередь наборов во входном семействе, приоритет которых определяется количеством оставшихся элементов, которые они охватывают. Каждый раз, когда жадный алгоритм выбирает набор как часть своего вывода, вновь покрытые элементы набора должны быть вычтены из приоритетов других наборов, которые их покрывают; в ходе работы алгоритма количество этих изменений приоритетов представляет собой просто сумму размеров входных наборов. Приоритетами являются монотонно убывающие целые числа, ограниченные сверху количеством охватываемых элементов. Каждый выбор жадного алгоритма включает в себя поиск набора с максимальным приоритетом, что можно сделать путем сканирования сегментов очереди сегментов вниз, начиная с самого последнего предыдущего максимального значения. Общее время линейно зависит от размера входных данных. ^[10]

Планирование

Очереди сегментов можно использовать для планирования задач с указанием сроков, например, при пересылке пакетов для интернет-данных с гарантиями качества обслуживания . Для этого приложения сроки должны быть разбиты на отдельные интервалы, а задачи, сроки выполнения которых попадают в один и тот же интервал, считаются имеющими эквивалентный приоритет. ^[2]

Вариант структуры данных квантованной очереди сегментов, календарная очередь , был применен для планирования моделирования дискретных событий , где элементами в очереди являются будущие события, приоритет которых определяется временем в рамках моделирования, когда события должны произойти. В этом приложении порядок событий имеет решающее значение, поэтому приоритеты не могут быть приблизительными. Таким образом, очередь календаря выполняет поиск элемента с минимальным приоритетом иначе, чем очередь сегментов: в очереди сегментов может быть возвращен любой элемент первого непустого сегмента, но вместо этого очередь календаря ищет все элементы в этот сегмент, чтобы определить, какой из них имеет наименьший неквантованный приоритет. Чтобы обеспечить быстроту поиска, этот вариант пытается сохранить количество сегментов пропорциональным количеству элементов, регулируя масштаб квантования и перестраивая структуру данных, когда она выходит из равновесия. В худшем случае календарные очереди могут быть медленнее, чем очереди сегментов (когда все элементы попадают в одну и ту же наименьшую корзину), но они работают быстрее, когда элементы равномерно распределены между сегментами, в результате чего средний размер сегмента остается постоянным. ^[20]^[21]

Быстрый марш

В прикладной математике и численных методах решения дифференциальных уравнений неопрятные очереди приоритетов используются для расстановки приоритетов шагов метода быстрого марша решения краевых задач уравнения Эйконала , используемого для моделирования распространения волн . Этот метод определяет моменты времени, в которые движущаяся граница пересекает набор дискретных точек (например, точек целочисленной сетки), используя метод определения приоритетов, напоминающий непрерывную версию алгоритма Дейкстры , а время его работы определяется очередью приоритетов. из этих точек. Его можно ускорить до линейного времени, округлив приоритеты, используемые в этом алгоритме, до целых чисел и используя очередь для этих целых чисел. Как и в алгоритмах Дейкстры и Дайала, приоритеты монотонны, поэтому при быстром марше можно использовать монотонную оптимизацию очереди сегментов и ее анализ. Однако дискретизация вносит некоторую погрешность в полученные расчеты. ^[4]

См. также

Мягкая куча , другой способ ускорения очереди приоритетов за счет использования приблизительных приоритетов.

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и Скиена, Стивен С. (1998), Руководство по разработке алгоритмов , Springer, стр. 181, ISBN 9780387948607 .
^ Перейти обратно: ^а ^б ^с Фигейра, Н.Р. (1997), «Решение проблемы приоритетной очереди для дисциплин обслуживания с указанием сроков», Труды Шестой Международной конференции по компьютерным коммуникациям и сетям , IEEE Computer Society Press, стр. 320–325, doi : 10.1109/icccn .1997.623330 , S2CID 5611516
^ Перейти обратно: ^а ^б Хенцингер, Моника ; Ноэ, Александр; Шульц, Кристиан (2019), «Точные минимальные сокращения общей памяти», Международный симпозиум IEEE по параллельной и распределенной обработке, 2019 г., IPDPS 2019, Рио-де-Жанейро, Бразилия, 20–24 мая 2019 г. , стр. 13–22, arXiv : 1808.05458 , doi : 10.1109/IPDPS.2019.00013 , S2CID 52019258
^ Перейти обратно: ^а ^б ^с Раш, Кристиан; Зацгер, Томас (2009), «Замечания о $реализации O (N)$ метода быстрого марша» (PDF) , IMA Journal of Numerical Analysis , 29 (3): 806–813, doi : 10.1093/imanum/drm028 , MR 2520171
^ Перейти обратно: ^а ^б Робледо, Алисия; Гивант, Хосе Э. (2010), «Очереди с псевдоприоритетами для производительности в реальном времени процессов динамического программирования, применяемых для планирования пути» (PDF) , в Уайете, Гордон; Апкрофт, Бен (ред.), Австралазийская конференция по робототехнике и автоматизации
^ Перейти обратно: ^а ^б Эделькамп, Стефан; Шредль, Стефан (2011), «3.1.1 Структуры данных сегментов» , Эвристический поиск: теория и приложения , Elsevier, стр. 90–92, ISBN 9780080919737 . См. также стр. 157 за историю и название этого сооружения.
^ Перейти обратно: ^а ^б ^с Дайал, Роберт Б. (1969), «Алгоритм 360: Лес кратчайшего пути с топологическим упорядочением [H]», Communications of the ACM , 12 (11): 632–633, doi : 10.1145/363269.363610 , S2CID 6754003 .
^ Перейти обратно: ^а ^б ^с Мельхорн, Курт ; Сандерс, Питер (2008), «10.5.1 Очереди сегментов» , «Алгоритмы и структуры данных: базовый набор инструментов» , Springer, стр. 201, ISBN 9783540779773 .
^ Перейти обратно: ^а ^б ^с ^д Берцекас, Дмитрий П. (1991), «Алгоритм Даала» , Оптимизация линейной сети: алгоритмы и коды , Кембридж, Массачусетс: MIT Press, стр. 72–75, ISBN 0-262-02334-2 , МР 1201582
^ Перейти обратно: ^а ^б Лим, CL; Моффат, Алистер; Вирт, Энтони Ян (2014), «Ленивый и энергичный подход к решению проблемы покрытия множеств» , Томас, Брюс; Парри, Дэйв (ред.), Тридцать седьмая Австралазийская конференция по информатике, ACSC 2014, Окленд, Новая Зеландия, январь 2014 г. , CRPIT, vol. 147, Австралийское компьютерное общество, стр. 19–27 . См., в частности, Раздел 2.4, «Приоритетная очередь», с. 22.
^ Джонсон, Дональд Б. (1981), «Очередь с приоритетами, в которой операции инициализации и очереди занимают $время O (log log D)$ », Mathematical Systems Theory , 15 (4): 295–309, doi : 10.1007/BF01786986 , MR 0683047 , S2CID 35703411
^ Матула, Дэвид В .; Бек, Л.Л. (1983), «Алгоритмы упорядочения, кластеризации и раскраски графов с наименьшим последним», Журнал ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR 0709826 , S2CID 4417741 .
^ Варгезе, Джордж (2005), Сетевые алгоритмы: междисциплинарный подход к проектированию быстрых сетевых устройств , Морган Кауфманн, стр. 78–80, ISBN 9780120884773 .
^ Перейти обратно: ^а ^б Феста, Паола (2006), «Алгоритмы кратчайшего пути», в Ресенде, Маурисио Г.К .; Пардалос, Панос М. (ред.), Справочник по оптимизации в телекоммуникациях , Бостон: Springer, стр. 185–210, doi : 10.1007/978-0-387-30165-5_8 ; см., в частности, раздел 8.3.3.6, «Реализация Dial», стр. 194–195.
^ Mehlhorn & Sanders (2008) (Упражнение 10.11, стр. 201) приписывают эту идею статье Э. А. Диница (Ефим Диниц) 1978 года.
^ Габоу, Гарольд Н .; Тарьян, Роберт Э. (1988), «Алгоритмы для решения двух узких задач оптимизации» , Журнал алгоритмов , 9 (3): 411–417, doi : 10.1016/0196-6774(88)90031-4 , MR 0955149
^ Динур, Ирит ; Стерер, Дэвид (2014), «Аналитический подход к параллельному повторению», в книге Шмойса, Дэвида Б. (редактор), Симпозиум по теории вычислений, STOC 2014, Нью-Йорк, Нью-Йорк, США, 31 мая – 3 июня 2014 г. , ACM, стр. 624–633, arXiv : 1305.1979 , doi : 10.1145/2591796.2591884 , MR 3238990 , S2CID 15252482
^ Джонсон, Дэвид С. (1974), «Алгоритмы аппроксимации комбинаторных задач», Журнал компьютерных и системных наук , 9 (3): 256–278, doi : 10.1016/S0022-0000(74)80044-9 , MR 0449012
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990], «Упражнение 35.3-3», Введение в алгоритмы (3-е изд.), MIT Press и McGraw-Hill, стр. 1122, ISBN 0-262-03384-4
^ Браун, Р. (октябрь 1988 г.), «Очереди календаря: быстрая $O(1)$ реализация очереди приоритетов для проблемы набора событий моделирования», Communications of the ACM , 31 (10): 1220–1227, doi : 10.1145/63039.63045 , S2CID 32086497
^ Эриксон, К. Брюс; Ладнер, Ричард Э .; ЛаМарка, Энтони (2000), «Оптимизация очередей статического календаря», Транзакции ACM по моделированию и компьютерному моделированию , 10 (3): 179–214, doi : 10.1145/361026.361028

[skiena-1] Перейти обратно: ^а ^б ^с ^д ^и Скиена, Стивен С. (1998), Руководство по разработке алгоритмов , Springer, стр. 181, ISBN 9780387948607 .

[figueira-2] Перейти обратно: ^а ^б ^с Фигейра, Н.Р. (1997), «Решение проблемы приоритетной очереди для дисциплин обслуживания с указанием сроков», Труды Шестой Международной конференции по компьютерным коммуникациям и сетям , IEEE Computer Society Press, стр. 320–325, doi : 10.1109/icccn .1997.623330 , S2CID 5611516

[hns-3] Перейти обратно: ^а ^б Хенцингер, Моника ; Ноэ, Александр; Шульц, Кристиан (2019), «Точные минимальные сокращения общей памяти», Международный симпозиум IEEE по параллельной и распределенной обработке, 2019 г., IPDPS 2019, Рио-де-Жанейро, Бразилия, 20–24 мая 2019 г. , стр. 13–22, arXiv : 1808.05458 , doi : 10.1109/IPDPS.2019.00013 , S2CID 52019258

[remarks-4] Перейти обратно: ^а ^б ^с Раш, Кристиан; Зацгер, Томас (2009), «Замечания о $реализации O (N)$ метода быстрого марша» (PDF) , IMA Journal of Numerical Analysis , 29 (3): 806–813, doi : 10.1093/imanum/drm028 , MR 2520171

[pseudo-5] Перейти обратно: ^а ^б Робледо, Алисия; Гивант, Хосе Э. (2010), «Очереди с псевдоприоритетами для производительности в реальном времени процессов динамического программирования, применяемых для планирования пути» (PDF) , в Уайете, Гордон; Апкрофт, Бен (ред.), Австралазийская конференция по робототехнике и автоматизации

[es-6] Перейти обратно: ^а ^б Эделькамп, Стефан; Шредль, Стефан (2011), «3.1.1 Структуры данных сегментов» , Эвристический поиск: теория и приложения , Elsevier, стр. 90–92, ISBN 9780080919737 . См. также стр. 157 за историю и название этого сооружения.

[dial-7] Перейти обратно: ^а ^б ^с Дайал, Роберт Б. (1969), «Алгоритм 360: Лес кратчайшего пути с топологическим упорядочением [H]», Communications of the ACM , 12 (11): 632–633, doi : 10.1145/363269.363610 , S2CID 6754003 .

[ms-8] Перейти обратно: ^а ^б ^с Мельхорн, Курт ; Сандерс, Питер (2008), «10.5.1 Очереди сегментов» , «Алгоритмы и структуры данных: базовый набор инструментов» , Springer, стр. 201, ISBN 9783540779773 .

[bertsekas-9] Перейти обратно: ^а ^б ^с ^д Берцекас, Дмитрий П. (1991), «Алгоритм Даала» , Оптимизация линейной сети: алгоритмы и коды , Кембридж, Массачусетс: MIT Press, стр. 72–75, ISBN 0-262-02334-2 , МР 1201582

[lmw-10] Перейти обратно: ^а ^б Лим, CL; Моффат, Алистер; Вирт, Энтони Ян (2014), «Ленивый и энергичный подход к решению проблемы покрытия множеств» , Томас, Брюс; Парри, Дэйв (ред.), Тридцать седьмая Австралазийская конференция по информатике, ACSC 2014, Окленд, Новая Зеландия, январь 2014 г. , CRPIT, vol. 147, Австралийское компьютерное общество, стр. 19–27 . См., в частности, Раздел 2.4, «Приоритетная очередь», с. 22.

[11] Джонсон, Дональд Б. (1981), «Очередь с приоритетами, в которой операции инициализации и очереди занимают $время O (log log D)$ », Mathematical Systems Theory , 15 (4): 295–309, doi : 10.1007/BF01786986 , MR 0683047 , S2CID 35703411

[12] Матула, Дэвид В .; Бек, Л.Л. (1983), «Алгоритмы упорядочения, кластеризации и раскраски графов с наименьшим последним», Журнал ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR 0709826 , S2CID 4417741 .

[varghese-13] Варгезе, Джордж (2005), Сетевые алгоритмы: междисциплинарный подход к проектированию быстрых сетевых устройств , Морган Кауфманн, стр. 78–80, ISBN 9780120884773 .

[festa-14] Перейти обратно: ^а ^б Феста, Паола (2006), «Алгоритмы кратчайшего пути», в Ресенде, Маурисио Г.К .; Пардалос, Панос М. (ред.), Справочник по оптимизации в телекоммуникациях , Бостон: Springer, стр. 185–210, doi : 10.1007/978-0-387-30165-5_8 ; см., в частности, раздел 8.3.3.6, «Реализация Dial», стр. 194–195.

[15] Mehlhorn & Sanders (2008) (Упражнение 10.11, стр. 201) приписывают эту идею статье Э. А. Диница (Ефим Диниц) 1978 года.

[16] Габоу, Гарольд Н .; Тарьян, Роберт Э. (1988), «Алгоритмы для решения двух узких задач оптимизации» , Журнал алгоритмов , 9 (3): 411–417, doi : 10.1016/0196-6774(88)90031-4 , MR 0955149

[17] Динур, Ирит ; Стерер, Дэвид (2014), «Аналитический подход к параллельному повторению», в книге Шмойса, Дэвида Б. (редактор), Симпозиум по теории вычислений, STOC 2014, Нью-Йорк, Нью-Йорк, США, 31 мая – 3 июня 2014 г. , ACM, стр. 624–633, arXiv : 1305.1979 , doi : 10.1145/2591796.2591884 , MR 3238990 , S2CID 15252482

[18] Джонсон, Дэвид С. (1974), «Алгоритмы аппроксимации комбинаторных задач», Журнал компьютерных и системных наук , 9 (3): 256–278, doi : 10.1016/S0022-0000(74)80044-9 , MR 0449012

[19] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990], «Упражнение 35.3-3», Введение в алгоритмы (3-е изд.), MIT Press и McGraw-Hill, стр. 1122, ISBN 0-262-03384-4

[20] Браун, Р. (октябрь 1988 г.), «Очереди календаря: быстрая $O(1)$ реализация очереди приоритетов для проблемы набора событий моделирования», Communications of the ACM , 31 (10): 1220–1227, doi : 10.1145/63039.63045 , S2CID 32086497

[21] Эриксон, К. Брюс; Ладнер, Ричард Э .; ЛаМарка, Энтони (2000), «Оптимизация очередей статического календаря», Транзакции ACM по моделированию и компьютерному моделированию , 10 (3): 179–214, doi : 10.1145/361026.361028

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]