Викиконспекты - Вклад участника [ru]

Двоичная куча

2012-03-08T20:52:18Z

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

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

{{Определение
|definition=
'''Двоичная куча''' или '''пирамида''' — такое двоичное дерево, для которого выполнены три условия:

* Значение (ключ) в любой вершине не больше (если куча для минимума), чем значения её потомков.

* Полное двоичное дерево, у которого могут отсутствовать некоторые листья последнего слоя.

* Последний слой заполняется слева направо.
}}

Удобная структура данных для сортирующего дерева — массив <tex>A</tex>, у которого первый элемент, <tex>A[1]</tex> — элемент в корне, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i]</tex> и <tex>A[2i+1]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{N})</tex>, где <tex>N</tex> — количество узлов дерева.

Кучи бывают как для минимума (когда предок не больше детей), так и для максимума (когда предок не меньше детей).

==Базовые процедуры==

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

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Sift_Down''' (просеивание вниз) и '''Sift_Up''' (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Sift_Down(i)'''.
Работа процедуры : если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем '''Sift_Down()''' для этого сына.
Процедура выполняется за время <tex>O(\log{N})</tex>.

<code>
Sift_Down(i)
left = 2 * i // левый сын
right = 2 * i + 1 // правый сын
// heap_size - количество элементов в куче
If (left ≤ A.heap_size) and (A[left] < A[i])
min = left
else
min = i
If (right ≤ A.heap_size) and (A[right] < A[i])
min = right
else
min = i
If (min <> i)
Поменять A[i] и A[minimum]
Sift_Down(min)
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией '''Sift_Up(i)'''.

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем '''Sift_Up''' для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{N})</tex>.

<code>
Sift_Up(i)
If (A[i] < A[i / 2])
Поменять A[i] и A[i / 2]
Sift_Up(i / 2)
</code>

===Извлечение минимального элемента===

Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{N})</tex>.
Извлечение выполняется в четыре этапа:
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается '''Sift_Down(i)''' для корня.
# Сохранённый элемент возвращается.
<code>
extract_min()
min = A[1]
A[1] = A[A.heap_size]
A.heap_size = A.heap_size - 1
Sift_Down(1)
return min
</code>

===Добавление нового элемента===

Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью

<code>
Insert(key)
A.heap_size = A.heap_size + 1
A[A.heap_size] = key
Sift_Up(A.heap_size)
</code>

== Источники ==
* [http://ru.wikipedia.org/wiki/Min-heap Двоичная куча]

Двоичная куча

2012-03-08T20:51:56Z

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

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

{{Определение
|definition=
'''Двоичная куча''' или '''пирамида''' — такое двоичное дерево, для которого выполнены три условия:

* Значение (ключ) в любой вершине не больше (если куча для минимума), чем значения её потомков.

* Полное двоичное дерево, у которого могут отсутствовать некоторые листья последнего слоя.

* Последний слой заполняется слева направо.
}}

Удобная структура данных для сортирующего дерева — массив <tex>A</tex>, у которого первый элемент, <tex>A[1]</tex> — элемент в корне, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i]</tex> и <tex>A[2i+1]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{N})</tex>, где <tex>N</tex> — количество узлов дерева.

Кучи бывают как для минимума (когда предок не больше детей), так и для максимума (когда предок не меньше детей).

==Базовые процедуры==

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

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Sift_Down''' (просеивание вниз) и '''Sift_Up''' (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Sift_Down(i)'''.
Работа процедуры : если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем '''Sift_Down()''' для этого сына.
Процедура выполняется за время <tex>O(\log{N})</tex>.

<code>
Sift_Down(i)
left = 2 * i // левый сын
right = 2 * i + 1 // правый сын
// heap_size - количество элементов в куче
If (left ≤ A.heap_size) and (A[left] < A[i])
min = left
else
min = i
If (right ≤ A.heap_size) and (A[right] < A[i])
min = right
else
min = i
If (min <> i)
Поменять A[i] и A[minimum]
Sift_Down(min)
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией '''Sift_Up(i)'''.

Работа процедуры : если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем '''Sift_Up''' для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{N})</tex>.

<code>
Sift_Up(i)
If (A[i] < A[i / 2])
Поменять A[i] и A[i / 2]
Sift_Up(i / 2)
</code>

===Извлечение минимального элемента===

Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{N})</tex>.
Извлечение выполняется в четыре этапа:
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается '''Sift_Down(i)''' для корня.
# Сохранённый элемент возвращается.
<code>
extract_min()
min = A[1]
A[1] = A[A.heap_size]
A.heap_size = A.heap_size - 1
Sift_Down(1)
return min
</code>

===Добавление нового элемента===

Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью

<code>
Insert(key)
A.heap_size = A.heap_size + 1
A[A.heap_size] = key
Sift_Up(A.heap_size)
</code>

== Источники ==
* [http://ru.wikipedia.org/wiki/Min-heap Двоичная куча]

Обсуждение:Двоичная куча

2012-03-08T20:50:54Z

178.66.50.23: /* Обсуждение */

== Замечания ==

{{tick | ticked = 1}} Кучи бывают не только для минимума, но и для максимума.
{{tick}} Привести оформление к единому [[Обсуждение:Дискретная математика и алгоритмы |стилю]].
{{tick}} Мелкие ошибки, вроде пропущенного пробела.
{{tick}} Добавить рисунок
{{tick}} Оформить ссылки

== Обсуждение ==

: Плохо определять двоичную кучу как двоичное дерево без определения двоичного дерева? --[[Участник:Rybak|Андрей Рыбак]] 04:13, 7 февраля 2012 (MSK)
Нужна отдельная статья для двоичного дерева (Редактор)

Обсуждение:Двоичная куча

2012-03-08T20:49:54Z

178.66.50.23: /* Замечания */

Двоичная куча

2012-03-08T20:48:31Z

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

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

{{Определение
|definition=
'''Двоичная куча''' или '''пирамида''' — такое двоичное дерево, для которого выполнены три условия:

* Значение (ключ) в любой вершине не больше (если куча для минимума), чем значения её потомков.

* Полное двоичное дерево, у которого могут отсутствовать некоторые листья последнего слоя.

* Последний слой заполняется слева направо.
}}

Удобная структура данных для сортирующего дерева — массив <tex>A</tex>, у которого первый элемент, <tex>A[1]</tex> — элемент в корне, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i]</tex> и <tex>A[2i+1]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{N})</tex>, где <tex>N</tex> — количество узлов дерева.

Кучи бывают как для минимума (когда предок не больше детей), так и для максимума (когда предок не меньше детей).

==Базовые процедуры==

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

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Sift_Down''' (просеивание вниз) и '''Sift_Up''' (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Sift_Down(i)'''.
Работа процедуры : если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем '''Sift_Down()''' для этого сына.
Процедура выполняется за время <tex>O(\log{N})</tex>.

<code>
Sift_Down(i)
left = 2 * i // левый сын
right = 2 * i + 1 // правый сын
// heap_size - количество элементов в куче
If (left ≤ A.heap_size) and (A[left] < A[i])
min = left
else
min = i
If (right ≤ A.heap_size) and (A[right] < A[i])
min = right
else
min = i
If (min <> i)
Поменять A[i] и A[minimum]
Sift_Down(min)
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией'''Sift_Up(i)'''.

Работа процедуры : если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем '''Sift_Up''' для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{N})</tex>.

<code>
Sift_Up(i)
If (A[i] < A[i / 2])
Поменять A[i] и A[i / 2]
Sift_Up(i / 2)
</code>

===Извлечение минимального элемента===

Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{N})</tex>.
Извлечение выполняется в четыре этапа:
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается '''Sift_Down(i)''' для корня.
# Сохранённый элемент возвращается.
<code>
extract_min()
min = A[1]
A[1] = A[A.heap_size]
A.heap_size = A.heap_size - 1
Sift_Down(1)
return min
</code>

===Добавление нового элемента===

Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью

<code>
Insert(key)
A.heap_size = A.heap_size + 1
A[A.heap_size] = key
Sift_Up(A.heap_size)
</code>

== Источники ==
* [http://ru.wikipedia.org/wiki/Min-heap Двоичная куча]