Редактирование: Толстая куча на избыточном счётчике

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 49: Строка 49:
 
Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log{n})</tex> деревьев.
 
Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log{n})</tex> деревьев.
 
|proof=
 
|proof=
 +
}}
 +
 +
{{Определение
 +
|id=def2
 +
|neat =
 +
|definition=
 +
'''Лес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.
 +
}}
 +
{{Определение
 +
|id=def3
 +
|neat =
 +
|definition=
 +
'''Узел''' (англ. ''Node'') в ''нагруженном лесе'' назовем '''неправильным''', если его ключ меньше ключа его родителя.
 +
}}
 +
{{Определение
 +
|id=def4
 +
|neat =
 +
|definition=
 +
'''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</tex>.
 
}}
 
}}
  
Строка 198: Строка 217:
 
===Корректировка при вставке ===
 
===Корректировка при вставке ===
 
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при вставке в кучу нового дерева ранга <tex>i~(\mathrm{insertTree(i,p)})</tex>. Эта процедура вставляет новое дерево ранга  <tex>i</tex> (на него указывает указатель <tex>p</tex>) в списочную часть  <tex>i</tex>-го разряда корневого счетчика <tex>\mathtt{rootCount}</tex> выглядит так:
 
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при вставке в кучу нового дерева ранга <tex>i~(\mathrm{insertTree(i,p)})</tex>. Эта процедура вставляет новое дерево ранга  <tex>i</tex> (на него указывает указатель <tex>p</tex>) в списочную часть  <tex>i</tex>-го разряда корневого счетчика <tex>\mathtt{rootCount}</tex> выглядит так:
  '''void''' insertTree('''int''' i, '''Node''' p):
+
  insertTree(i, p):
 
   p1 = rootCount[i].listPointer
 
   p1 = rootCount[i].listPointer
 
   '''if''' rootCount[i].Value <tex> \ne </tex> 0
 
   '''if''' rootCount[i].Value <tex> \ne </tex> 0
Строка 209: Строка 228:
 
===Корректировка при удалении===
 
===Корректировка при удалении===
 
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при удалении из кучи дерева ранга <tex>i~(\mathrm{deleteTree(i,p)})</tex>. Эта процедура удаляет дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) из списочной части  <tex>i</tex>-го разряда корневого счетчика <tex>\mathtt{rootCount}</tex> . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:
 
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при удалении из кучи дерева ранга <tex>i~(\mathrm{deleteTree(i,p)})</tex>. Эта процедура удаляет дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) из списочной части  <tex>i</tex>-го разряда корневого счетчика <tex>\mathtt{rootCount}</tex> . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:
  '''void''' deleteTree('''int''' i, '''Node''' p):
+
  deleteTree(i, p):
 
   p1 = rootCount[i].listPointer
 
   p1 = rootCount[i].listPointer
 
   '''if''' p1 == p
 
   '''if''' p1 == p
 
     rootCount[i].listPointer = p.right
 
     rootCount[i].listPointer = p.right
 
   j = 1
 
   j = 1
   '''while''' (j <tex> \leqslant </tex> rootCount[i].Value) '''and''' (p1.right <tex> \ne </tex> p):
+
   '''while''' (j <tex> \le </tex> rootCount[i].Value) '''and''' (p1.right <tex> \ne </tex> p):
 
     j++
 
     j++
 
     p1 = p1.right
 
     p1 = p1.right
Строка 222: Строка 241:
 
'''Связывание''' <tex>\mathrm{fastening (p1, p2, p3)}</tex> трех толстых деревьев ранга <tex>i</tex> в одно толстое дерево ранга <tex>i+1</tex>. Эта функция принимает три указателя <tex>p1, p2 ,p3</tex>  на три разных толстых дерева одного и того же ранга <tex>i</tex>  и возвращает указатель на вновь сформированное дерево ранга <tex>i+1</tex> .
 
'''Связывание''' <tex>\mathrm{fastening (p1, p2, p3)}</tex> трех толстых деревьев ранга <tex>i</tex> в одно толстое дерево ранга <tex>i+1</tex>. Эта функция принимает три указателя <tex>p1, p2 ,p3</tex>  на три разных толстых дерева одного и того же ранга <tex>i</tex>  и возвращает указатель на вновь сформированное дерево ранга <tex>i+1</tex> .
 
Процедура заключается в выполнении следующего псевдокода:
 
Процедура заключается в выполнении следующего псевдокода:
  '''Node''' fastening('''Node''' p1, '''Node''' p2, '''Node''' p3):
+
  fastening (p1, p2, p3):
   '''if''' (p1.key <tex> \leqslant </tex> p2.key) '''and''' (p1.Key <tex> \leqslant </tex> p3.key)
+
   '''if''' (p1.key <tex> \le </tex> p2.key) '''and''' (p1.Key <tex> \le </tex> p3.key)
 
     minP = p1
 
     minP = p1
 
     p1 = p2
 
     p1 = p2
 
     p2 = p3
 
     p2 = p3
   '''if''' (p2.key <tex> \leqslant </tex> p1.key) '''and''' (p2.key <tex> \leqslant </tex> p3.key)
+
   '''if''' (p2.key <tex> \le </tex> p1.key) '''and''' (p2.key <tex> \le </tex> p3.key)
 
     minP = p2
 
     minP = p2
 
     p1 = p1
 
     p1 = p1
 
     p2 = p3
 
     p2 = p3
   '''if''' (p3.key <tex> \leqslant </tex> p1.key) '''and''' (p3.key <tex> \leqslant </tex> p2.key)
+
   '''if''' (p3.key <tex> \le </tex> p1.key) '''and''' (p3.key <tex> \le </tex> p2.key)
 
     minP = p3
 
     minP = p3
 
     p1 = p1
 
     p1 = p1
Строка 252: Строка 271:
 
Функция <tex>\mathrm{getKey(p)}</tex> по указателю p на элемент определяет значение его ключа:
 
Функция <tex>\mathrm{getKey(p)}</tex> по указателю p на элемент определяет значение его ключа:
 
  <font color=green>//под <tex>\infty</tex> нужно понимать нейтральный относительно минимума элемент.</font>
 
  <font color=green>//под <tex>\infty</tex> нужно понимать нейтральный относительно минимума элемент.</font>
  '''int''' getKey('''Node''' p):
+
  getKey(p):
 
   '''if''' p == NULL
 
   '''if''' p == NULL
 
     min = <tex>\infty</tex>
 
     min = <tex>\infty</tex>
Строка 262: Строка 281:
  
 
Функция <tex>\mathrm{minKeyNodeRoot(p)}</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:
 
Функция <tex>\mathrm{minKeyNodeRoot(p)}</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:
  '''Node''' minKeyNodeRoot('''Node''' p):
+
  minKeyNodeRoot(p):
 
   p1 = p
 
   p1 = p
 
   minP = p1
 
   minP = p1
Строка 274: Строка 293:
 
Операция фиксации <tex>\mathrm{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>\mathrm{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>\mathtt{maxRank}</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>\mathtt{maxRank}</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
 
Следует учесть, что ранг нового дерева может стать больше, чем <tex>\mathtt{maxRank}</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>\mathtt{maxRank}</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
  '''void''' rmFixRootCount('''int''' i)
+
  rmFixRootCount(i)
 
   '''if''' maxRank == i
 
   '''if''' maxRank == i
 
     maxRank = i + 1
 
     maxRank = i + 1
Строка 292: Строка 311:
 
===Инкрементирование i-го разряда корневого счетчика===
 
===Инкрементирование i-го разряда корневого счетчика===
 
По сравнению с описанным алгоритмом инкрементирования <tex>i</tex>-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
 
По сравнению с описанным алгоритмом инкрементирования <tex>i</tex>-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
  '''void''' rmIncRootCount('''int''' i, '''Node''' p)
+
  rmIncRootCount(i,p)
 
   '''if''' (rootCount[i].Value == 1) '''or''' (rootCount[i].Value == 2)
 
   '''if''' (rootCount[i].Value == 1) '''or''' (rootCount[i].Value == 2)
 
     '''if''' rootCount[rootCount[i].forwardPointer].Value == 3
 
     '''if''' rootCount[rootCount[i].forwardPointer].Value == 3
Строка 306: Строка 325:
 
===Удаление дерева из кучи===
 
===Удаление дерева из кучи===
 
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>i</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
 
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>i</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
  '''void''' delete('''int''' i, '''Node''' p):
+
  delete(i, p):
 
   deleteTree(i, p)
 
   deleteTree(i, p)
 
   rootCount[i].Value = rootCount[i].Value - 1
 
   rootCount[i].Value = rootCount[i].Value - 1
  
 
===Нахождение дерева с минимальным ключом в корне <tex>\mathrm{minKey()}</tex>===
 
===Нахождение дерева с минимальным ключом в корне <tex>\mathrm{minKey()}</tex>===
  '''Node''' minKey()
+
  minKey()
 
   minP = NULL
 
   minP = NULL
 
   '''for''' i = 0 to maxRank:
 
   '''for''' i = 0 to maxRank:
Строка 395: Строка 414:
 
===deleteViolation===
 
===deleteViolation===
 
Для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
 
Для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
  '''void''' deleteViolation('''Node''' h2):
+
  deleteViolation(h2):
 
   '''for''' i = 0 '''to''' h2.maxRank
 
   '''for''' i = 0 '''to''' h2.maxRank
 
     '''if''' countViolation[i].Value == 2
 
     '''if''' countViolation[i].Value == 2
Строка 404: Строка 423:
 
       fixCountViolation(i)
 
       fixCountViolation(i)
  
==См. также==
+
==Источники==
* [[Тонкая куча]]
 
 
 
==Источники информации==
 
 
* [http://www.intuit.ru/studies/courses/100/100/lecture/2935?page=1 INTUIT.ru {{---}} Толстые кучи]
 
* [http://www.intuit.ru/studies/courses/100/100/lecture/2935?page=1 INTUIT.ru {{---}} Толстые кучи]
 
* [https://www.lektorium.tv/lecture/14234  CS center {{---}} Приоритетные очереди]
 
* [https://www.lektorium.tv/lecture/14234  CS center {{---}} Приоритетные очереди]
Строка 414: Строка 430:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)