Radix куча - Radix heap

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Сентябрь 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

А куча системы счисления это структура данных для реализации операций очередь с монотонным приоритетом. Затем можно управлять набором элементов, которым назначен ключ. Время выполнения операций зависит от разницы между наибольшим и наименьшим ключом или константой. Структура данных состоит в основном из ряда ведра, размер которых увеличивается экспоненциально.

Предпосылки

1. все ключи натуральные числа;
2. Максимум. ключ - мин. ключ ${ displaystyle leq}$ C для постоянной C;
3. то экстракт мин операция монотонный; то есть значения, возвращаемые последовательными экстракт мин звонки монотонно возрастающий.

Описание структуры данных

Три самых важных поля находятся:

1. ${ displaystyle b}$ размера ${ Displaystyle B: = lfloor log (C + 1) rfloor +1}$с наименьшим индексом 0 хранит сегменты;
2. ${ displaystyle u}$ размера ${ displaystyle B + 1}$с 0 в качестве наименьшего индекса сохранить (нижние) границы сегментов;
3. ${ displaystyle bNum}$, выполняется для каждого элемента ${ displaystyle x}$ в куче ведро, в котором он хранится.

На диаграмме выше показана структура данных. Применяются следующие инварианты:

1. ${ Displaystyle и [я] leq}$ ключ в ${ Displaystyle б [я] <и [я + 1]}$: ключи в ${ Displaystyle б [я]}$ вверх или вниз по значению в ${ Displaystyle и [я + 1]}$ или же ${ Displaystyle и [я]}$ ограничено.
2. ${ displaystyle u [0] = 0, u [1] = u [0] + 1, u [B] = infty}$ и ${ Displaystyle 0 Leq U [я + 1] -u [я] Leq 2 ^ {я-1}}$ за ${ Displaystyle я = 1, ldots, В-1}$: размеры ведер увеличиваются в геометрической прогрессии.

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

Операции

В течение инициализация, генерируются пустые сегменты и нижние границы ${ displaystyle u}$ генерируются (согласно инварианту 2); Продолжительность ${ Displaystyle О (В)}$.

В течение вставлять, новый элемент ${ displaystyle x}$ линейно перемещается справа налево по ковшам, а новый элемент с ${ Displaystyle к (х)}$ хранится в левом ведре к этому ${ Displaystyle и [я] GEQ К (х)}$; Продолжительность ${ Displaystyle О (В)}$.

За клавиша уменьшения, сначала уменьшается значение ключа (проверка на соответствие инвариантам). Затем ${ displaystyle bNum}$ поле используется для определения местоположения элемента и при необходимости повторяется слева, аналогично вставлять операция. Время работы ${ displaystyle O (1)}$ (амортизировано).

В экстракт мин операция удаляет элемент из корзины ${ displaystyle b [0]}$ и возвращает его. Если ведро ${ displaystyle b [0]}$ еще не пусто, операция прекращена. Если, однако, оно пустое, ищется следующее большее непустое ведро, его наименьший элемент ${ displaystyle k}$ отслеживается и ${ displaystyle u [0]}$ установлен на k (для этого требуется монотонность). Затем, согласно инвариантам, границы ведра переопределяются и элементы удаляются. ${ Displaystyle б [я]}$ к новообразованным ведрам; Продолжительность ${ displaystyle O (1)}$ (амортизировано).

Если отображается, поле ${ displaystyle bNum}$ обновлено.

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

• Б.В. Черкасский, А.В. Гольдберг, К. Сильверштейн: Сегменты, кучи, списки и очереди с монотонным приоритетом (Абстрактный ), в: Материалы восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Январь 1997 г., стр. 83–92.