Radix куча является структурой данных для реализации операций в приоритетной очереди монотонного . Затем можно управлять набором элементов, которым назначен ключ. Время выполнения операций зависит от разницы между наибольшим и наименьшим ключом или константой. Структура данных состоит в основном из серии сегментов , размер которых увеличивается в геометрической прогрессии .
Предпосылки
- все ключи - натуральные числа ;
- Максимум. ключ - мин. ключ C для постоянной C;
- экстракт мин операция монотонна; то есть значения, возвращаемые последовательными вызовами extract-min , монотонно увеличиваются .
Описание структуры данных
Три наиболее важных поля :
- размера с наименьшим индексом 0 хранит сегменты;
- размера , с 0 в качестве самого низкого индекса, сохранить (нижние) границы сегментов;
- , выполняется для каждого элемента в куче ведро, в котором он хранится.
На приведенной выше диаграмме показана структура данных. Применяются следующие инварианты:
- ключ в : ключи в вверх или вниз по значению в или же ограничено.
- а также для : размеры ведер увеличиваются в геометрической прогрессии.
Важно отметить экспоненциальный рост пределов (и, следовательно, диапазона, удерживаемого корзиной). Таким образом, логарифмическая зависимость величин поля имеет значение C, максимальное различие между двумя ключевыми значениями.
Операции
Во время инициализации генерируются пустые сегменты, а нижние границыгенерируются (согласно инварианту 2); Продолжительность.
Во время вставки новый элемент линейно перемещается справа налево по ковшам, а новый элемент с хранится в левом ведре к этому ; Продолжительность.
Для ключа уменьшения сначала уменьшается значение ключа (проверка на соответствие инвариантам). ЗатемПоле используется для поиска элемента и при необходимости повторяется слева, аналогично операции вставки . Время работы (амортизировано).
Операция extract-min удаляет элемент из корзиныи возвращает его. Если ведроеще не пусто, операция прекращена. Если, однако, оно пустое, ищется следующее большее непустое ведро, его наименьший элемент отслеживается и установлен на k (для этого требуется монотонность). Затем, согласно инвариантам, переопределяются границы ведра и удаляются элементы.к новообразованным ведрам; Продолжительность (амортизировано).
Если отображается, поле обновлено.
Рекомендации
- Б. В. Черкасский, А. В. Гольдберг, К. Сильверштейн: корзины, кучи, списки и очереди с монотонным приоритетом ( аннотация ) // Материалы восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Январь 1997 г., стр. 83–92.