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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:30:48Z

rollbackEdits.php mass rollback

185.100.85.24 в 04:33, 1 сентября 2022

2022-09-01T04:33:23Z

212.102.57.138: /* Извлечение минимального элемента */ форматирование

2020-08-01T22:42:07Z

‎Извлечение минимального элемента: форматирование

94.188.6.74: /* Поиск k-ого элемента */

2019-10-27T00:14:38Z

‎Поиск k-ого элемента

5.18.249.29: /* Определение */

2019-07-13T22:38:00Z

‎Определение

178.130.7.83: /* Построение кучи за O(n) */

2019-01-09T20:22:21Z

‎Построение кучи за O(n)

78.30.250.135: /* Построение кучи за O(n) */

2019-01-06T14:04:27Z

‎Построение кучи за O(n)

Shchuko: /* Наивная реализация */

2019-01-06T11:40:31Z

‎Наивная реализация

Shchuko: /* Восстановление свойств кучи */

2019-01-06T11:17:24Z

‎Восстановление свойств кучи

109.252.76.59: /* siftUp */

2018-04-23T17:04:11Z

‎siftUp

← Предыдущая		Версия 16:30, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	==Определение==		==Определение==
	{{Определение		{{Определение

← Предыдущая		Версия 04:33, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	==Определение==		==Определение==
	{{Определение		{{Определение

@@ Строка 65: / Строка 65: @@
 # Сохранённый элемент возвращается.
   '''int''' extractMin():
       '''int''' min = a[0]
@@ Строка 72: / Строка 71: @@
       siftDown(0)
       '''return''' min
 ===Добавление нового элемента===

@@ Строка 149: / Строка 149: @@
 </code>
-===Поиск k-ого элемента===
+===Поиск k-ого элемента (очень коряво расписано с неверными индексами)===
 Требуется найти <tex>k</tex>-ый по величине элемент в куче.

@@ Строка 4: / Строка 4: @@
 '''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:
-* Значение в любой вершине не меньше (если куча для максимума), чем значения её потомков.
+* Значение в любой вершине не больше (если куча для минимума), чем значения её потомков.
 * На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
 * Последний слой заполнен слева направо (как показано на рисунке)

@@ Строка 96: / Строка 96: @@
 {{Лемма
 |statement= На выходе получим искомую кучу.
-|proof= При вызове <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами. После выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей.  Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
+|proof= До вызова <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами. После выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей.  Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
 }}
 {{Лемма

@@ Строка 123: / Строка 123: @@
 Псевдокод алгоритма:
 <code style="display:inline-block">
-  '''function''' heapify():
+  '''function''' buldHeap():
       '''for''' i = a.heapSize / 2 '''downto''' 0
           siftDown(i)

@@ Строка 134: / Строка 134: @@
 <code style="display:inline-block">
   '''function''' merge(a, b : '''Heap'''):
-      '''while''' b.heapSize <tex>\neq</tex> 0
+      '''while''' b.heapSize > 0
           a.insert(b.extractMin())
 </code>
 ====Реализация с помощью построения кучи====
 Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(n + m)</tex>.

@@ Строка 22: / Строка 22: @@
 Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
 и <tex> \mathrm {siftUp} </tex> (просеивание вверх).
 Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.
 Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
 Процедура выполняется за время <tex>O(\log{n})</tex>.
-====siftDown====
 <code style="display:inline-block">
   '''function''' siftDown(i : '''int'''):

@@ Строка 48: / Строка 48: @@
 <code style="display:inline-block">
   '''function''' siftUp(i : '''int'''):
-      '''while''' a[i] <tex><</tex> a[(i - 1) / 2]     <font color = "green">// i <tex>==</tex> 0 {{---}} мы в корне</font>
+      '''while''' a[i] < a[(i - 1) / 2]     <font color = "green">// i <tex>==</tex> 0 {{---}} мы в корне</font>
           swap(a[i], a[(i - 1) / 2])
           i = (i - 1) / 2