Структуры данных и модели вычислений
Основные операции
Операция make-heap заключается в инициализации счетчиков. Трудоемкость .
Операция FindMinвозвращает указатель на минимальный элемент. Трудоемкость .
Операция Insert(key). Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
Операция уменьшения ключа DecreaseKey. Чтобы выполнить эту операцию, поступим следующим образом. Пусть— узел, на который указывает указатель . Вычитаемиз ключа узла . Если новый ключ меньше минимального ключа кучи , обмениваем ключ элементас ключом минимального элемента. Новых нарушений операция не создаст. Пусть — ранг. Если — нарушаемый узел, добавляемкак новое-ранговое нарушение инкрементированием-й цифрысчетчика нарушений. Трудоемкость .
Операция DeleteMin выполняется следующим образом. Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом. Трудоемкость операции равна .
Операция удаления элемента. Выполняется с помощьюи затем. Трудоемкость операции .
Операция Meld(h1, h2). Выполняется следующим образом. Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча —. Пройти по счетчику нарушений от младшей цифры к старшей, пропуская цифры со значением .
