Радикс-куча

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

Предварительные условия

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

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

Три наиболее важных поля :

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

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

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

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

Операции

Во время инициализации генерируются пустые сегменты и нижние границы $u$ генерируются (согласно инварианту 2); время работы $O(B)$.

Во время вставки новый элемент $x$ линейно перемещается справа налево через сегменты и новый элемент с $k(x)$ хранится в левом ведре для этого $u[i]\geq k(x)$; время работы $O(B)$.

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

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

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

Ссылки

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