Фибоначчиева куча - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:39:24Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:37, 1 сентября 2022

2022-09-01T03:37:29Z

178.67.196.226: /* Соедининение двух куч */

2021-10-25T01:10:37Z

‎Соедининение двух куч

178.67.196.226: /* Структура */

2021-10-25T01:09:32Z

‎Структура

145.255.139.98: /* Удаление минимального элемента */

2020-05-08T10:06:13Z

‎Удаление минимального элемента

91.228.178.74: /* Уменьшение значения элемента */

2019-12-22T21:54:14Z

‎Уменьшение значения элемента

93.185.27.94: Иначе мы присвоим x.parent.child = x, что не то, что нам надо

2019-04-10T09:58:00Z

Иначе мы присвоим x.parent.child = x, что не то, что нам надо

92.242.59.6: /* Реализация */

2018-11-28T08:32:09Z

‎Реализация

Gaporf: /* Уменьшение значения элемента */ орфографическая ошибка в слове структура

2018-10-24T11:03:45Z

‎Уменьшение значения элемента: орфографическая ошибка в слове структура

188.170.72.75: /* Реализация */

2018-10-22T14:05:55Z

‎Реализация

@@ Строка 1: / Строка 1: @@
-{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
+'''Фибоначчиева куча''' (англ. ''Fibonacci heap'')  {{---}} структура данных, отвечающая интерфейсу [[Приоритетные очереди#Операции | приоритетная очередь]]. Эта структура данных имеет меньшую [[Амортизационный анализ#Основные определения | амортизированную  сложность]], чем такие приоритетные очереди как [[Биномиальная куча | биномиальная куча]] и [[Двоичная куча | двоичная куча]]. Изначально эта структура данных была разработана Майклом Фридманом<ref>[[wikipedia:en:Michael_Fredman | Майкл Фридман {{---}} Википедия]]</ref> и Робертом Тарьяном<ref>[[wikipedia:en:Robert_Tarjan | Роберт Тарьян {{---}} Википедия]]</ref> при работе по улучшению асимптотической сложности [[Алгоритм Дейкстры | алгоритма Дейкстры]]. Свое название Фибоначчиева куча получила  из-за использования некоторых свойств  чисел Фибоначчи<ref>[[wikipedia:en:Fibonacci_number | Числа Фибоначчи {{---}} Википедия]]</ref> в [[Амортизационный анализ#Метод потенциалов | потенциальном анализе]] этой реализации.
 == Структура ==
 Фибоначчиева куча  {{---}} набор из [[Дерево, эквивалентные определения | подвешенных деревьев]] удовлетворяющих свойству: каждый предок не больше своих детей(если дерево на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одно из главных преимуществ Фибоначчиевой кучи {{---}} гибкость её структуры из-за того, что на деревья не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.
@@ Строка 85: / Строка 64: @@
 </code>
 ==== Соедининение двух куч ====
-Для сливания двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую  два списка вершины, которых подаются ей в качестве аргументов.
+Для сливания двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую  два списка вершины, которых подаются ей в качестве аргументов.
 <code style="display:inline-block">
   '''function''' unionLists(first: '''Node''', second: '''Node'''):

@@ Строка 1: / Строка 1: @@
-'''Фибоначчиева куча''' (англ. ''Fibonacci heap'')  {{---}} структура данных, отвечающая интерфейсу [[Приоритетные очереди#Операции | приоритетная очередь]]. Эта структура данных имеет меньшую [[Амортизационный анализ#Основные определения | амортизированную  сложность]], чем такие приоритетные очереди как [[Биномиальная куча | биномиальная куча]] и [[Двоичная куча | двоичная куча]]. Изначально эта структура данных была разработана Майклом Фридманом<ref>[[wikipedia:en:Michael_Fredman | Майкл Фридман {{---}} Википедия]]</ref> и Робертом Тарьяном<ref>[[wikipedia:en:Robert_Tarjan | Роберт Тарьян {{---}} Википедия]]</ref> при работе по улучшению асимптотической сложности [[Алгоритм Дейкстры | алгоритма Дейкстры]]. Свое название Фибоначчиева куча получила  из-за использования некоторых свойств  чисел Фибоначчи<ref>[[wikipedia:en:Fibonacci_number | Числа Фибоначчи {{---}} Википедия]]</ref> в [[Амортизационный анализ#Метод потенциалов | потенциальном анализе]] этой реализации.
+{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 == Структура ==
 Фибоначчиева куча  {{---}} набор из [[Дерево, эквивалентные определения | подвешенных деревьев]] удовлетворяющих свойству: каждый предок не больше своих детей(если дерево на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одно из главных преимуществ Фибоначчиевой кучи {{---}} гибкость её структуры из-за того, что на деревья не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.
@@ Строка 64: / Строка 85: @@
 </code>
 ==== Соедининение двух куч ====
-Для сливания двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую  два списка вершины, которых подаются ей в качестве аргументов.
+Для сливания двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую  два списка вершины, которых подаются ей в качестве аргументов.
 <code style="display:inline-block">
   '''function''' unionLists(first: '''Node''', second: '''Node'''):

@@ Строка 64: / Строка 64: @@
 </code>
 ==== Соедининение двух куч ====
-Для сливание двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую  два списка вершины, которых подаются ей в качестве аргументов.
+Для сливания двух Фибоначчиевых куч необходимо просто объединить их корневые списки, а также обновить минимум новой кучи, если понадобится. Вынесем в вспомогательную функцию <tex>unionLists</tex> логику, объединяющую  два списка вершины, которых подаются ей в качестве аргументов.
 <code style="display:inline-block">
   '''function''' unionLists(first: '''Node''', second: '''Node'''):
@@ Строка 88: / Строка 88: @@
          min = that.min
 </code>
 ==== Удаление минимального элемента====
 Первая рассматриваемая операция, в ходе которой значительно меняется структура кучи. Здесь используется вспомогательная процедура <tex>consolidate</tex>, благодаря которой собственно и достигается желанная амортизированная оценка. В данном случае <tex> min = \varnothing</tex> не рассматривается и считается нарушением предусловий <tex>deleteMin</tex>

@@ Строка 1: / Строка 1: @@
 '''Фибоначчиева куча''' (англ. ''Fibonacci heap'')  {{---}} структура данных, отвечающая интерфейсу [[Приоритетные очереди#Операции | приоритетная очередь]]. Эта структура данных имеет меньшую [[Амортизационный анализ#Основные определения | амортизированную  сложность]], чем такие приоритетные очереди как [[Биномиальная куча | биномиальная куча]] и [[Двоичная куча | двоичная куча]]. Изначально эта структура данных была разработана Майклом Фридманом<ref>[[wikipedia:en:Michael_Fredman | Майкл Фридман {{---}} Википедия]]</ref> и Робертом Тарьяном<ref>[[wikipedia:en:Robert_Tarjan | Роберт Тарьян {{---}} Википедия]]</ref> при работе по улучшению асимптотической сложности [[Алгоритм Дейкстры | алгоритма Дейкстры]]. Свое название Фибоначчиева куча получила  из-за использования некоторых свойств  чисел Фибоначчи<ref>[[wikipedia:en:Fibonacci_number | Числа Фибоначчи {{---}} Википедия]]</ref> в [[Амортизационный анализ#Метод потенциалов | потенциальном анализе]] этой реализации.
 == Структура ==
-Фибоначчиева куча  {{---}} набор из [[Дерево, эквивалентные определения | подвешенных деревьев]] удовлетворяющих свойству: каждый предок не больше своих детей(если дерево на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одним из главных преимуществ Фибоначчиевой кучи {{---}} гибкость её структуры из-за того, что на деревья не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.
+Фибоначчиева куча  {{---}} набор из [[Дерево, эквивалентные определения | подвешенных деревьев]] удовлетворяющих свойству: каждый предок не больше своих детей(если дерево на минимум). Это означает, что минимум всей кучи это один из корней этих деревьев. Одно из главных преимуществ Фибоначчиевой кучи {{---}} гибкость её структуры из-за того, что на деревья не наложены никакие ограничения по форме. Например, Фибоначчиева куча может состоять хоть из деревьев в каждом из которых по одному элементу. Такая гибкость позволяет выполнять некоторые операции лениво, оставляя работу более поздним операциям. Далее будут даны некоторые определения, которые понадобятся в дальнейшем.
 {{Определение
 |definition=
@@ Строка 10: / Строка 10: @@
 '''Степень кучи''' (англ. ''degree'')  {{---}} наибольшая степень вершины этой кучи. Далее будем обозначать как <tex>degree(H)</tex>, где <tex>H</tex> это куча.
 }}
 == Реализация ==
 [[File:Fibonacci-heap.png|thumb|340px|Пример фибоначчиевой кучи]]

@@ Строка 100: / Строка 100: @@
          min <tex>= \varnothing</tex>
          '''return'''
-     min = min.right <span style="color:#008000">              // пока что перекинем указаиель min на правого сына, а далее consolidate() скорректирует min в процессе выполнения</span>
+     min = min.right <span style="color:#008000">              // пока что перекинем указатель min на правого сына, а далее consolidate() скорректирует min в процессе выполнения</span>
      consolidate()
      size--

@@ Строка 189: / Строка 189: @@
      '''Node''' parent = x.parent <span style="color:#008000">    // иначе вызываем cut и cascadingCut</span>
      cut(x)
-     cascadingCut(x.parent)
+     cascadingCut(parent)
 </code>
 ===== Вырезание =====

@@ Строка 199: / Строка 199: @@
      R.left = L <span style="color:#008000">               // аккуратно удаляем текущую вершину</span>
      L.right = R
      x.parent.degree--
      '''if''' x.parent.child = x <span style="color:#008000">  // чтобы родитель не потерял ссылку на сыновей проверяем: </span>
@@ Строка 207: / Строка 205: @@
          '''else'''
              x.parent.child = x.right
      x.parent <tex>= \varnothing</tex>
      unionLists(min, x) <span style="color:#008000">       // вставляем наше поддерево в корневой список</span>

@@ Строка 22: / Строка 22: @@
      '''int''' degree <span style="color:#008000">  // степень вершины</span>
      '''boolean''' mark <span style="color:#008000">// был ли удален в процессе изменения ключа ребенок этой вершины)</span>
-</code>Также стоит упомянуть, что нам нужен указатель только на одного ребенка, поскольку остальные хранятся в двусвязном списке с ним. Для доступа ко всей куче нам тоже нужен всего один элемент, поэтому разумно хранить именно указатель на минимум кучи(он обязательно один из корней), а для получения размера за константное время будем хранить размер кучи отдельно.
+</code>Также стоит упомянуть, что нам нужен указатель только на одного ребенка, поскольку остальные хранятся в двусвязном списке с ним. Для доступа ко всей куче нам тоже нужен всего один элемент, поэтому разумно хранить именно указатель на минимум кучи (он обязательно один из корней), а для получения размера за константное время будем хранить размер кучи отдельно.
 <code style="display:inline-block">
   '''struct''' fibonacciHeap

@@ Строка 184: / Строка 184: @@
 <code style="display:inline-block">
   '''function''' decreaseKey(x: '''Node''', newValue: '''int'''):
-     '''if''' newValue > x.parent.key <span style="color:#008000"> // если после изменения структкра дерева сохранится, то меняем и выходим</span>
+     '''if''' newValue > x.parent.key <span style="color:#008000"> // если после изменения структура дерева сохранится, то меняем и выходим</span>
          x.key = newValue
          '''return'''

@@ Строка 19: / Строка 19: @@
      '''Node''' child <span style="color:#008000">  // указатель на один из дочерних узлов</span>
      '''Node''' left <span style="color:#008000">   // указатель на левый узел того же предка</span>
-     '''Node''' right <span style="color:#008000">  // указатель на правый узел того же предка</span>
+     '''Node''' right <span style="color:#009000">  // указатель на правый узел того же предка</span>
      '''int''' degree <span style="color:#008000">  // степень вершины</span>
      '''boolean''' mark <span style="color:#008000">// был ли удален в процессе изменения ключа ребенок этой вершины)</span>