Структуры данных и модели вычислений
Эта функция принимает три указателя
Эта функция принимает три указателя на три разных толстых дерева одного и того же ранга и возвращает указатель на вновь сформированное дерево ранга .
Процедура заключается в выполнении операторов
Функция GetKey (p) по указателю p на элемент определяет значение его ключа и реализуется оператором
Функция MinKeyNodeRoot(p), которая по указателю на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом, реализуется операторами
Очевидно, что трудоемкость всех приведенных выше операций оценивается величиной .
Операция фиксации ({\rm FixRootCount(i)}) Операция фиксации -го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга , состоящий ровно из трех деревьев. При выполнении этой операции значение в -м разряде — должно стать равным нулю, а значение в -м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга , а количество деревьев ранга должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга , связать их в дерево ранга и вставить вновь полученное дерево в кучу.
Следует учесть, что ранг нового дерева может стать больше, чем , что потребует инициализации нового разряда. Для этого необходимо увеличить значение на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
Операция фиксации осуществляется с помощью операторов
Очевидно, что если списочная часть корневого счетчика до операции соответствовала избыточному корневому представлению, то и после операции фиксации это соответствие сохранится. Сохраняется также и регулярность представления. Трудоемкость данной операции .
Инкрементирование i-го разряда корневого счетчика ({\rm IncRootCount(i,p)}). По сравнению с описанным алгоритмом инкрементирования -го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели. Процедура реализуется операторами
Очевидно, что, если корневой счетчик находится в корректном состоянии и , то операция инкрементирования -го разряда корневого счетчика переводит корневой счетчик в новое корректное состояние.
