Кинетический нагреватель - Kinetic heater
А Кинетический нагреватель это кинетическая приоритетная очередь похожий на кинетическая куча, который использует рандомизацию для упрощения своего анализа аналогично трогать. В частности, каждый элемент имеет связанный с ним случайный ключ в дополнение к его приоритету (который изменяется как непрерывная функция времени, как и все кинетические структуры данных ). Тогда кинетический нагреватель одновременно двоичное дерево поиска на клавишах элементов и куча по приоритетам элементов. Кинетический нагреватель достигает (ожидаемых) границ асимптотической производительности, равных лучшим кинетическим приоритетным очередям. Однако на практике это менее эффективно, поскольку необходимо хранить дополнительные случайные ключи, а процедура обработки сбоя сертификата представляет собой (относительно сложную) ротацию, а не простой обмен.[1]
Выполнение
Если у каждого элемента есть ключ и связанный с ним приоритет, тогда существует уникальная древовидная структура, которая одновременно является деревом поиска по ключам и кучей по приоритетам - эта структура соответствует treap (если приоритеты выбраны случайным образом) или кинетический нагреватель (если ключи выбраны случайно).
Достоверность древовидной структуры обеспечивается созданием сертификата на каждом краю, который применяет свойство кучи на этом краю. Основное рабочее различие между кинетической кучей и кинетическим нагревателем заключается в том, как они реагируют на отказы сертификатов. Когда сертификат на грани выходит из строя, кинетический нагреватель выполняет вращение вокруг узлов, которые вышли из строя (вместо замены, которую выполняла бы кинетическая куча).
Например, рассмотрим элементы B (с родителем F) и его левый потомок D (с правым ребенком C). Когда сертификат [B>D] на краю BD не удается, дерево будет повернутый по этому краю. Таким образом, в этом случае результирующая структура имеет D на месте B, C становится ребенком B вместо тогоD, и есть три изменения сертификата: [B> D] заменено на [D> B], [D> C] заменено на [B> C] и [F> B] заменено на [F> D]. Все остальное остается прежним.
Анализ
Эта кинетическая структура данных:
- Отзывчивый: Существует O (1) обновлений сертификатов, которые необходимо выполнить при сбое сертификата, что занимает время O (log n).
- Местный: Каждый элемент участвует в O (1) сертификатах
- Компактный: Всего сертификатов O (n)
- Эффективный: Он имеет ту же (ожидаемую) асимптотическую производительность, что и кинетическая подвеска, кинетический турнир - для набора пространственно-временных траекторий, где каждая пара пересекает не более s раз кинетический нагреватель обрабатывает O (λс + 2журнал п) события вO (λс + 2журнал2п) время, где λс + 2 это Последовательность Давенпорта-Шинцеля.
Рекомендации
- ^ да Фонсека, Гильерме Д. и де Фигейредо, Селина М. Х. и Карвалью, Пауло К. П. «Кинетическая вешалка» (PDF). Письма об обработке информации. С. 151–157. Архивировано из оригинал (PDF) 24 мая 2015 г.. Получено 17 мая, 2012.CS1 maint: несколько имен: список авторов (ссылка на сайт)
Basch, J. «Кинетические структуры данных». Получено 17 мая, 2012.