Radix-куча - Radix heap
 | Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. (Сентябрь 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
А куча системы счисления это структура данных для реализации операций очередь с монотонным приоритетом. Затем можно управлять набором элементов, которым назначен ключ. Время выполнения операций зависит от разницы между наибольшим и наименьшим ключом или константой. Структура данных состоит в основном из ряда ведра, размер которых увеличивается экспоненциально.
Предпосылки
- все ключи натуральные числа;
- Максимум. ключ - мин. ключ C для постоянной C;
- то экстракт мин операция монотонный; то есть значения, возвращаемые последовательными экстракт мин звонки монотонно возрастающий.
Описание структуры данных
Три самых важных поля находятся:
- размера с наименьшим индексом 0 хранит сегменты;
- размера с 0 в качестве наименьшего индекса сохранить (нижние) границы сегментов;
- , выполняется для каждого элемента в куче ведро, в котором он хранится.
На диаграмме выше показана структура данных. Применяются следующие инварианты:
- ключ в : ключи в вверх или вниз по значению в или же ограничено.
- и за : размеры ведер увеличиваются в геометрической прогрессии.
![{ Displaystyle и [я] leq}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb849ffee274aaf0ddb3607cac7f7a68d8fc5c25)
![{ Displaystyle б [я] <и [я + 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54716130aa632ba0cc4defabaa93bc6eaf8b8afc)
![{ Displaystyle б [я]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/136ab44f7e12bba6f295358dcb75c190770e8246)
![{ Displaystyle и [я + 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4970f89b73d9215ddedce08a0cb73525c50cc90b)
![{ Displaystyle и [я]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14709ec9b6a8bdd01fa3ff37617dfd01896f4996)
![{ displaystyle u [0] = 0, u [1] = u [0] + 1, u [B] = infty}](https://wikimedia.org/api/rest_v1/media/math/render/svg/743f603344041657aae7cc051c3ab7d5f2f5ed3c)
![{ Displaystyle 0 Leq U [я + 1] -u [я] Leq 2 ^ {я-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be37bcc3d484749f4c9215600b3f0b7637f4720d)
Важно отметить экспоненциальный рост пределов (и, следовательно, диапазона, удерживаемого корзиной). Таким образом, логарифмическая зависимость величин поля имеет значение C, максимальное различие между двумя ключевыми значениями.
Операции
В течение инициализация, генерируются пустые сегменты и нижние границы генерируются (согласно инварианту 2); Продолжительность .
В течение вставлять, новый элемент линейно перемещается справа налево по ковшам, а новый элемент с хранится в левом ведре к этому ; Продолжительность .
![{ Displaystyle и [я] GEQ К (х)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e3ed3a6b5ca533ba7ca217469176136fdf78977)
За клавиша уменьшения, сначала уменьшается значение ключа (проверка на соответствие инвариантам). Затем поле используется для определения местоположения элемента и при необходимости повторяется слева, аналогично вставлять операция. Время работы (амортизировано).
В экстракт мин операция удаляет элемент из корзины и возвращает его. Если ведро еще не пусто, операция прекращена. Если, однако, оно пустое, ищется следующее большее непустое ведро, его наименьший элемент отслеживается и установлен на k (для этого требуется монотонность). Затем, согласно инвариантам, границы ведра переопределяются и элементы удаляются. к новообразованным ведрам; Продолжительность (амортизировано).
![{ displaystyle b [0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a006e3551c0f8c667fb17aba6fd47740abfcf9a)
![{ displaystyle u [0]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/191b3e901d62b40a1d6232a105aff57f5bea9798)
Если отображается, поле обновлено.
Рекомендации
- Б.В. Черкасский, А.В. Гольдберг, К. Сильверштейн: Сегменты, кучи, списки и очереди с монотонным приоритетом (Абстрактный ), в: Материалы восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Январь 1997 г., стр. 83–92.