Radix куча - Radix heap

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

Предпосылки

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

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

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

  1. размера с наименьшим индексом 0 хранит сегменты;
  2. размера с 0 в качестве наименьшего индекса сохранить (нижние) границы сегментов;
  3. , выполняется для каждого элемента в куче ведро, в котором он хранится.

RadixHeap1.png

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

  1. ключ в : ключи в вверх или вниз по значению в или же ограничено.
  2. и за : размеры ведер увеличиваются в геометрической прогрессии.

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

Операции

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

В течение вставлять, новый элемент линейно перемещается справа налево по ковшам, а новый элемент с хранится в левом ведре к этому ; Продолжительность .

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

В экстракт мин операция удаляет элемент из корзины и возвращает его. Если ведро еще не пусто, операция прекращена. Если, однако, оно пустое, ищется следующее большее непустое ведро, его наименьший элемент отслеживается и установлен на k (для этого требуется монотонность). Затем, согласно инвариантам, границы ведра переопределяются и элементы удаляются. к новообразованным ведрам; Продолжительность (амортизировано).

Если отображается, поле обновлено.

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