Изменения

Перейти к: навигация, поиск

Толстая куча на избыточном счётчике

178 байт убрано, 19:29, 9 апреля 2016
→‎Основные операции
==Основные операции==
Рассмотрим операции, которые можно производить с толстой кучей. Время работы основных операций указано в таблице:
{| class="wikitable" style="width:10cm" border=1
|+
|}
* <tex>\mathrm{===makeHeap}</tex> {{---}} <tex>O(1)</tex>===Заключается в инициализации счетчиков. * <tex>\mathrm{ ===findMin}</tex> {{---}} <tex>O(1)</tex>===Возвращает указатель на минимальный элемент. * <tex>\mathrm{ ===insert(key)}</tex> {{---}} <tex>O(1)</tex>===
Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга <tex>0</tex> в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
* <tex>\mathrm{===decreaseKey}</tex> {{---}} <tex>O(1)</tex>===
Чтобы выполнить эту операцию, поступим следующим образом. Пусть <tex>x</tex> — узел, на который указывает указатель <tex>p</tex> . Вычитаем <tex>\delta</tex> из ключа узла <tex>x</tex> . Если новый ключ <tex>x</tex> меньше минимального ключа кучи <tex>H</tex>, обмениваем ключ элемента <tex>p</tex> с ключом минимального элемента. Новых нарушений операция не создаст. Пусть <tex>r</tex> — ранг <tex>x</tex> . Если <tex>x</tex> — нарушаемый узел, добавляем <tex>x</tex> как новое <tex>r</tex>-ранговое нарушение инкрементированием <tex>r</tex>-й цифры <tex>d_r</tex> счетчика нарушений.
* <tex>\mathrm{===deleteMin}</tex> {{---}} <tex>O(\log(n))</tex>===
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
* <tex>\mathrm{===delete}</tex> {{---}} <tex>O(\log(n))</tex>===
Выполняем <tex>\mathrm{decreaseKey}</tex> а затем <tex>\mathrm{deleteMin}</tex>.
* <tex>\mathrm{===meld(h1, h2)}</tex> {{---}} <tex>O(\log(n))</tex>===Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — <tex>р2</tex> . Пройти по счетчику нарушений <tex>p2</tex> от младшей цифры к старшей, пропуская цифры со значением <tex>0</tex> . Для <tex>i</tex>-й цифры <tex>d_i != 0</tex> делаем операцию фиксирования на каждой цифре, показываемой прямым указателем <tex>d_i</tex> , если эта цифра имеет значение <tex>2</tex>. Затем, если <tex>d_i = 2</tex> , фиксируем <tex>d_i</tex> . Если <tex>d_i = 1</tex> , преобразуем это <tex>i</tex>-ранговое нарушение в <tex>(i+1)</tex>-ранговое нарушение, как при фиксировании, используя <tex>i</tex>-рангового брата нарушенного узла вместо (несуществующего) другого <tex>i</tex> -рангового нарушения.Как только <tex>h2</tex> не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика <tex>h2</tex> в корневой счетчик <tex>h1</tex> инкрементированием соответствующих цифр. Если минимальный узел <tex>h2</tex> содержит меньший ключ, чем минимальный узел <tex>h1</tex> , следует установить новым минимальным узлом <tex>h1</tex> минимальный узел <tex>h2</tex> . Затем нужно вернуть модифицированную кучу <tex>h1</tex> в качестве результата <tex>\mathrm{meld}</tex> . * <tex>\mathrm{ ===deleteViolation}</tex>===
Для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
deleteViolation(h2):
Sokolova
635
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/53141»

Навигация