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

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

Внимание! Вы не авторизовались на сайте. Ваш 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>.
 
}}
 
}}
  
Строка 214: Строка 233:
 
     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
Строка 223: Строка 242:
 
Процедура заключается в выполнении следующего псевдокода:
 
Процедура заключается в выполнении следующего псевдокода:
 
  '''Node''' fastening('''Node''' p1, '''Node''' p2, '''Node''' p3):
 
  '''Node''' fastening('''Node''' p1, '''Node''' p2, '''Node''' 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
Строка 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:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
 

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

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

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