Изменения

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

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

332 байта убрано, 11:17, 9 апреля 2016
Нет описания правки
===Фиксация цифры===
Фиксацией цифры <tex>b</tex>, стоящей в <tex>i</tex>-м разряде представления <tex>d</tex>, (fix(i)) назовем операцию, заключающуюся в обнулении цифры <tex>d_i</tex> и инкрементировании цифры <tex> d_{i+1} </tex>, при этом если <tex>i=n</tex> , то полагаем <tex>d_{i+1} = 1</tex>. При каждом выполнении операции фиксации будем обновлять значение <tex>L'(i)</tex>. Очевидно, при <tex>b>2</tex> операцию <tex>fix(i)</tex> можно выполнить следующим образом:
<code> fixMMM fix('''int''' i): '''if''' d[i] == b d[i] = 0 d[i + 1]++ '''if''' d[i + 1] == b - 1: L'[i] = L'[i + 1] '''else''' L'[i] = i + 1</code>
===Инкремент===
Инкрементирование <tex>i</tex>-й цифры избыточного представления <tex>d</tex> <tex>inc(i)</tex> можно выполнить так:
<code> inc('''int''' i): fix(i) '''if''' (d[i] == b - 1) '''or''' (d[i] == b - 2) fix(L'[i]) d[i]++ fix(i)</code>
===Декремент===
===Обновление прямого указателя===
Обновление прямого указателя <tex>i</tex>-го разряда корневого счетчика заключается в выполнении следующего псевдокода:
<code> updateForwardPionter('''int''' i): '''if''' rootCount[i + 1].Value == 3 - 1 rootCount[i].forwardPointer = rootCount[i + 1].forwardPointer '''else''' rootCount[i].forwardPointer = i + 1</code>
===Корректировка при вставке ===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при вставке в кучу нового дерева ранга <tex>i~(insertTree(i,p))</tex>. Эта процедура вставляет новое дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) в списочную часть <tex>i</tex>-го разряда корневого счетчика <tex>rootCount</tex> выглядит так:
insertTree(i, p):
p1 = rootCount[i].listPointer
'''if''' rootCount[i].Value <tex> \ne </tex> 0
p.right = p1
'''else'''
p.right = NULL
p.left = NULL
rootCount[i].listPointer = p
<code>
insertTree(i, p):
p1 = rootCount[i].listPointer
'''if''' rootCount[i].Value <tex> \ne </tex> 0
p.right = p1
'''else'''
p.right = NULL
p.left = NULL
rootCount[i].listPointer = p
</code>
===Корректировка при удалении===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при удалении из кучи дерева ранга <tex>i~(deleteTree(i,p))</tex>. Эта процедура удаляет дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) из списочной части <tex>i</tex>-го разряда корневого счетчика <tex>rootCount</tex> . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:
deleteTree(i, p):
p1 = rootCount[i].listPointer
'''if''' p1 == p
rootCount[i].listPointer = p.right
j = 1
'''while''' (j <tex> \le </tex> rootCount[i].Value) '''and''' (p1.right <tex> \ne </tex> p):
j++
p1 = p1.right
p1.right = p.right
<code>
deleteTree(i, p):
p1 = rootCount[i].listPointer
'''if''' p1 == p
rootCount[i].listPointer = p.right
j = 1
'''while''' (j <tex> \le </tex> rootCount[i].Value) '''and''' (p1.right <tex> \ne </tex> p):
j++
p1 = p1.right
p1.right = p.right
</code>
===Связывание трех деревьев в одно===
'''Связывание''' <tex>(fastening (p1, p2, p3))</tex> трех толстых деревьев ранга <tex>i</tex> в одно толстое дерево ранга <tex>i+1</tex>. Эта функция принимает три указателя <tex>(p1, p2 ,p3)</tex> на три разных толстых дерева одного и того же ранга <tex>i</tex> и возвращает указатель на вновь сформированное дерево ранга <tex>i+1</tex> .
Процедура заключается в выполнении следующего псевдокода:
 <code> fastening (p1, p2, p3): '''if''' (p1.key <tex> \le </tex> p2.key) '''and''' (p1.Key <tex> \le </tex> p3.key) minP = p1 p1 = p2 p2 = p3 '''if''' (p2.key <tex> \le </tex> p1.key) '''and''' (p2.key <tex> \le </tex> p3.key) minP = p2 p1 = p1 p2 = p3 '''if''' (p3.key <tex> \le </tex> p1.key) '''and''' (p3.key <tex> \le </tex> p2.key) minP = p3 p1 = p1 p2 = p2 p1.right = p2 p1.left = NULL p1.parent = minP p2.right = minP.lChild p2.left = p1 p2.parent = minP '''if''' minP.lChild <tex> \ne </tex> NULL minP.lChild.left = p2 minP.lChild = p1 minP.rank = minP.rank + 1 minP.right = NULL minP.left = NULL '''return''' minP</code>
===Значение ключа элемента по указателю===
Функция <tex>getKey(p)</tex> по указателю p на элемент определяет значение его ключа:
 <code> // ''под <tex>\infty</tex> нужно понимать нейтральный относительно минимума элемент.'' getKey(p): '''if''' p == NULL min = <tex>\infty</tex> '''else''' min = p.key '''return''' min </code>
===Узел с минимальным ключом===
Функция <tex>minKeyNodeRoot(p)</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:
<code> minKeyNodeRoot(p): p1 = p minP = p1 '''while''' p1 <tex> \ne </tex> NULL '''if''' p1.key < minP.key minP = p1 p1 = p1.right '''return''' minP</code>
===Операция фиксации <tex>rmFixRootCount(i)</tex>===
Операция фиксации <tex>i</tex>-го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга <tex>i</tex>, состоящий ровно из трех деревьев. При выполнении этой операции значение в <tex>i</tex>-м разряде — должно стать равным нулю, а значение в <tex>i</tex>-м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга <tex>i</tex>, а количество деревьев ранга <tex>i+1</tex> должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга <tex>i</tex> , связать их в дерево ранга <tex>i+1</tex> и вставить вновь полученное дерево в кучу.
Следует учесть, что ранг нового дерева может стать больше, чем <tex>maxRank</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>maxRank</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
 <code> rmFixRootCount(i) '''if''' maxRank == i maxRank = i + 1 rootCount[i + 1].Value = 0 countViolation[i + 1].Value = 0 '''else''' updateForwardPointer(i + 1) rootCount[i].Value = 0 p1 = rootCount[i].listPointer p2 = p1.right p3 = p2.right p = fastening(p1, p2, p3) rootCount[i].listPointer = NULL insertTree(i + 1, p) rootCount[i + 1].Value = rootCount[i + 1].Value + 1 </code>
===Инкрементирование i-го разряда корневого счетчика===
По сравнению с описанным алгоритмом инкрементирования <tex>i</tex>-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
 <code> rmIncRootCount(i,p) '''if''' (rootCount[i].Value == 1) '''or''' (rootCount[i].Value == 2) '''if''' rootCount[rootCount[i].forwardPointer].Value == 3 fixRootCount(rootCount[i].forwardPointer); '''if''' rootCount[i].Value == 3 fixRootCount(i) insertTree(i, p) rootCount[i].Value = rootCount[i].Value + 1 updateForwardPointer(i) '''if''' rootCount[i].Value == 3 fixRootCount(i)</code>
===Удаление дерева из кучи===
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>i</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
<code> delete(i, p): deleteTree(i, p) rootCount[i].Value = rootCount[i].Value - 1</code>
===Нахождение дерева с минимальным ключом в корне (<tex>minKey()</tex>)===
 <code> minKey() minP = NULL '''for''' i = 0 to maxRank: p1 = minKeyNodeRoot(rootCount[i].listPointer) '''if''' getKey(p1) < getKey(minP): minP = p1 '''return''' minP</code>
==Счетчик нарушений==
* <tex>deleteViolation</tex>
Для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
 <code> deleteViolation(h2): '''for''' i = 0 '''to''' h2.maxRank '''if''' countViolation[i].Value == 2 fixCountViolation(i) '''for''' i = 0 to h2.maxRank '''if''' countViolation[i].Value == 1 incCountViolation(i, searchBrother(countViolation[i].rmFirstviolation)) fixCountViolation(i)</code>
=Источники=
Sokolova
635
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/53115»

Навигация