Структуры данных и модели вычислений
й разряд, равный количеству деревьев
которые интерпретируем следующим образом:
- — - й разряд, равный количеству деревьев ранга ;
- — прямой указатель -го разряда;
- — указатель на список деревьев ранга , присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя
корневых узлов связываемых деревьев. Если в куче нет деревьев ранга , то указатель заземлен. Заметим, что если значение равно нулю, то нам неважно, каково значение указателя .
Инициализация корневого счетчика (InitRootCount). Поскольку корневой счетчик реализован как массив записей, возникает вопрос о величине данного массива и о том, что делать, когда весь этот массив заполнен. Чтобы была возможность оценить время инициализации счетчиков величиной , используем поразрядную их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную , которая показывает нам, какая часть массивов счетчиков используется в данный момент.
При начальной инициализации необходимо установить счетчики в состояние, которое отвечает пустой куче. Очевидно, что в пустой куче не может быть никаких нарушений. Операция инициализации выглядит следующим образом.
Обновление прямого указателя i-го разряда корневого счетчика заключается в выполнении операторов
Корректировка списочной части i-го разряда корневого счетчика при вставке в кучу нового дерева ранга i. Эта процедура вставляет новое дерево ранга
(на него указывает указатель ) в списочную часть -го разряда корневого счетчика и заключается в выполнении операторов
Корректировка списочной части i>-го разряда корневого счетчика при удалении из кучи дерева ранга i. Эта процедура удаляет дерево ранга (на него указывает указатель ) из списочной части -го разряда корневого счетчика . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении операторов
Связывание (Fastening (p1, p2, p3)) трех толстых деревьев ранга i в одно толстое дерево ранга i +1.Эта функция принимает три указателя на три разных толстых дерева одного и того же ранга и возвращает указатель на вновь сформированное дерево ранга .
