Кинетическая вешалка - Kinetic hanger

А Кинетическая вешалка это рандомизированная версия кинетическая куча производительность которых легко проанализировать. Кинетическая подвеска удовлетворяет свойству кучи (приоритет каждого элемента выше, чем приоритет его дочерних элементов), но смягчает требование о том, что древовидная структура должна быть строго сбалансирована, поэтому вставки и удаления могут быть рандомизированы. В результате структура кинетической подвески обладает тем свойством, что она вычерчивается равномерно случайным образом из пространства всех возможных кучообразных структур на ее элементах.

Выполнение

Кинетическая конструкция подвески (в том числе сертификаты и очередь событий) точно такая же, как и структура кинетической кучи, но без требования балансировки. Таким образом, он состоит из эффективный приоритетная очередь (очередь событий) для поддержания времени отказа сертификата, а также основная (не обязательно сбалансированная) куча -подобно дерево структура, в которой хранятся элементы. С каждым ребром связан сертификат, который применяет свойство кучи (приоритет родителя> приоритет потомка) вдоль этого ребра.

Характерная работа кинетической подвески: "висит", который определяется следующим образом (делается различие между узлом в древовидной структуре и элементом, хранящимся в нем).Зависание (узел n, элемент e)

Если в п, положить е в п и вернуться
Если элемент Икс в п имеет более высокий приоритет, чем е, выберите ребенка c из п случайно и рекурсивно вызывать Повесить (c, e)
Если элемент Икс в п имеет более низкий приоритет, чем е, положить е в п выбрать ребенка c из п случайно и рекурсивно вызывать Повесить (c, x)

Основное отличие кинетической подвески от кинетической кучи заключается в ключевых операциях, которые в кинетической подвеске реализуются следующим образом:

Сборка-вешалка: Сначала отсортируйте элементы по приоритету, а затем вызовите вешать по корню для каждого элемента по порядку. Затем рассчитайте и запланируйте время отказа сертификата в очереди событий. Это занимает O (n log n) времени, аналогично кинетической куче.
Вставлять: Кинетическая подвеска вставляется сверху вниз (вместо снизу вверх) на "висит"новый элемент в корневом узле. Это занимает O (log n) времени, но O (log n) сертификатов, возможно, придется изменить на пути вниз, таким образом, общее время равно O $(бревно 2 п)$
Удалить: Это более простая операция, чем в куче, поскольку не требуется поддерживать балансировку древовидной структуры. Таким образом, элемент просто заменяется более крупным из его дочерних элементов, а затем этот дочерний элемент рекурсивно удаляется. Опять же, это занимает время O (log n), но, возможно, потребуется обновить сертификаты O (log n), поэтому общее время равно O $(бревно 2 п)$ .

Все эти операции приводят к равномерно случайной структуре подвески с ожидаемой высотой O (log n).

Анализ

Эта структура:

Отзывчивый: обработка сбоя сертификата занимает время O (log n), как в кинетической куче
Местный: каждый элемент участвует в сертификатах O (1), как в кинетической куче
Компактный: Всего сертификатов O (n), как в кинетической куче
Эффективный: он имеет такую же эффективность, как и кинетический турнир или же кинетический нагреватель - для набора пространственно-временных траекторий, где каждая пара пересекается не более чем $s$ раз кинетическая подвеска обрабатывает $O (λ s +2 бревно п)$ события в $O (λ s +2 бревно 2 п)$ время, где $λ s +2$ это Последовательность Давенпорта-Шинцеля

Кинетическая вешалка - Kinetic hanger

Выполнение

Анализ

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