Очередь с кинетическим приоритетом - Kinetic priority queue

А Кинетическая приоритетная очередь является Абстрактные кинетическая структура данных. Это вариант приоритетная очередь разработан для поддержания максимального (или минимального) приоритетного элемента (пары ключ-значение), когда приоритет каждого элемента изменяется как непрерывная функция времени. Очереди с кинетическим приоритетом использовались в качестве компонентов нескольких кинетических структур данных, а также для решения некоторых важных некинетических проблем, таких как проблема k-множества и проблема пересечения связанных красных синих сегментов.

Реализации

Поддерживаемые операции:

• создать очередь(q): создать пустую очередь кинетического приоритета q
• find-max(q, t) (или же find-min): - вернуть Максимум (или же мин для мин-очередь) значение хранится в очереди q в текущее виртуальное время т.
• вставлять(Икс, f_Икс, т): - вставьте ключ Икс в кинетическую очередь в текущее виртуальное времят, значение которой изменяется как непрерывная функция ж_Икс(т) времени т.
• Удалить(Икс, т) - удалить ключ Икс в текущее виртуальное время т.

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

Временные сложности реализации кинетической приоритетной очереди ^[2]

Траектория приоритетов элементов	Кинетическая куча	Кинетическая вешалка, обогреватель и турнир	Динамическая выпуклая оболочка
Линии	${\displaystyle O(n\log ^{2}n)}$	${\displaystyle O(n\log ^{2}n)}$	${\displaystyle O(n\log n)}$
Сегменты линии	${\displaystyle O(m{\sqrt {n}}\log ^{\frac {3}{2}}n)}$	${\displaystyle O(m\alpha (n)\log ^{2}n)}$	${\displaystyle O(m\log n\log \log n)}$
δ-пересекающиеся кривые	${\displaystyle O(n^{2}\log n)}$	${\displaystyle O(\lambda _{\delta }(n)\log n)}$	н / д

Здесь, ${\displaystyle \alpha (x)}$ обозначает обратная функция Аккермана.${\displaystyle \delta }$-пересекающиеся кривые относятся к кривым, где каждая пара имеет не более ${\displaystyle \delta }$ перекрестки и ${\displaystyle \lambda _{\delta }(n)}$ относится к термину в Последовательность Давенпорта-Шинцеля, что дает максимальный размер верхнего конверта ${\displaystyle n}$ ${\displaystyle \delta -}$пересекающиеся кривые. ${\displaystyle n}$ - наибольшее количество элементов в очереди в любой момент времени, а ${\displaystyle m}$ относится к общему количеству элементов, когда-либо находящихся в очереди.

Приложения

Очереди с кинетическим приоритетом используются как часть других структур / алгоритмов кинетических данных, таких как кинетическая ближайшая пара, кинетический max-cut^[3] или же кинетическая кластеризация.^[4]

Их также можно использовать для решения таких проблем, как расписание вещания^[5] или проблема пересечения связанных красно-синих сегментов.^[6]

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

1. Brodal, G.S .; Джейкоб, Р. (2002). «Динамическая плоская выпуклая оболочка». Proc. 43-й ежегодный симпозиум IEEE по основам компьютерных наук. FCS. С. 617–626. arXiv:1902.11169. Дои:10.1109 / SFCS.2002.1181985.
2. да Фонсека, Гильерме Д. и де Фигейредо, Селина М. Х. и Карвалью, Пауло К. П. «Кинетическая вешалка» (PDF). Письма об обработке информации. С. 151–157. Архивировано из оригинал (PDF) 24 мая 2015 г.. Получено 17 мая, 2012.
3. Czumaj, Артур; Фралинг, Гереон; Солер, Кристиан (2007). Эффективные кинетические структуры данных для MaxCut (PDF). Канадская конференция по вычислительной геометрии. Получено 17 мая, 2012.
4. Ли, Ифань; Хан, Цзявэй; Ян, Цзюн. «Кластеризация движущихся объектов». Материалы десятой международной конференции ACM SIGKDD по открытию знаний и интеллектуальному анализу данных. SIGKDD. ACM. С. 617–622.
5. К. Х., Тарьян Р. и Т. К. (2001). «Более быстрые кинетические кучи и их использование при планировании трансляций». Proc. 12-й симпозиум ACM-SIAM по дискретным алгоритмам. ACM. С. 836–844. CiteSeerX  10.1.1.12.2739.
6. Баш, Жюльен; Гибас, Леонид; Рамкумар, Г. (1996). Сообщение о красно-синих пересечениях между двумя наборами связанных сегментов линии. Springer Berlin / Heidelberg. CiteSeerX  10.1.1.55.98. Дои:10.1007/3-540-61680-2_64. ISBN  978-3-540-61680-1.