Радикальная куча

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

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью, добавив ссылки на дополнительные источники . Найти источники:  «Radix heap» – новости  · газеты  · книги  · ученый  · JSTOR ( май 2024 г. )

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

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

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

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

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

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

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

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

Во время вставки новый элемент линейно перемещается справа налево по контейнерам, и новый элемент сохраняется в левом контейнере до тех пор , пока не наступит время выполнения .${\displaystyle x}$${\displaystyle к(х)}$${\displaystyle u[i]\geq k(x)}$${\displaystyle O(B)}$

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

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

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

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