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

Дерево поиска, наивная реализация

2019-01-07T18:38:16Z

78.30.250.135: /* См. также Добавлена ссылка на статью про АВЛ-дерево*/

[[Файл:Binary_search_tree.svg.png|right|300px|thumb|Бинарное дерево поиска из 9 элементов]]'''Бинарное дерево поиска''' (англ. ''binary search tree, BST'') {{---}} структура данных для работы с [[Упорядоченное множество|упорядоченными множествами]].
Бинарное дерево поиска обладает следующим свойством: если <tex>x</tex> {{---}} узел бинарного дерева с ключом <tex>k</tex>, то все узлы в левом поддереве должны иметь ключи, меньшие <tex>k</tex>, а в правом поддереве большие <tex>k</tex>.
== Операции в бинарном дереве поиска ==
Для представления бинарного дерева поиска в памяти будем использовать следующую структуру:
'''struct''' Node:
'''T''' key // ключ узла
'''Node''' left // указатель на левого потомка
'''Node''' right // указатель на правого потомка
'''Node''' parent // указатель на предка

=== Обход дерева поиска ===
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов:
* <tex>\mathrm{inorderTraversal}</tex> {{---}} обход узлов в отсортированном порядке,
* <tex>\mathrm{preorderTraversal}</tex> {{---}} обход узлов в порядке: вершина, левое поддерево, правое поддерево,
* <tex>\mathrm{postorderTraversal}</tex> {{---}} обход узлов в порядке: левое поддерево, правое поддерево, вершина.
'''func''' inorderTraversal(x : '''Node'''):
'''if''' x != ''null''
inorderTraversal(x.left)
'''print''' x.key
inorderTraversal(x.right)
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 3 4 6 7 8 10 13 14''.

'''func''' preorderTraversal(x : '''Node''')
'''if''' x != ''null''
'''print''' x.key
preorderTraversal(x.left)
preorderTraversal(x.right)
При выполнении данного обхода вершины будут выведены в следующем порядке: ''8 3 1 6 4 7 10 14 13''.

'''func''' postorderTraversal(x : '''Node''')
'''if''' x != ''null''
postorderTraversal(x.left)
postorderTraversal(x.right)
'''print''' x.key
При выполнении данного обхода вершины будут выведены в следующем порядке: ''1 4 7 6 3 13 14 10 8''.

Данные алгоритмы выполняют обход за время <tex>O(n)</tex>, поскольку процедура вызывается ровно два раза для каждого узла дерева.

=== Поиск элемента ===
[[Файл:Bst search.png|frame|right|318px|Поиск элемента 4]]
Для поиска элемента в бинарном дереве поиска можно воспользоваться следующей функцией, которая принимает в качестве параметров корень дерева и искомый ключ. Для каждого узла функция сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае функция вызывается рекурсивно для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
<div style="width: 65%">
'''Node''' search(x : '''Node''', k : '''T'''):
'''if''' x == ''null'' '''or''' k == x.key
'''return''' x
'''if''' k < x.key
'''return''' search(x.left, k)
'''else'''
'''return''' search(x.right, k)
</div>

=== Поиск минимума и максимума ===
Чтобы найти минимальный элемент в бинарном дереве поиска, необходимо просто следовать указателям <tex>left</tex> от корня дерева, пока не встретится значение <tex>null</tex>. Если у вершины есть левое поддерево, то по свойству бинарного дерева поиска в нем хранятся все элементы с меньшим ключом. Если его нет, значит эта вершина и есть минимальная. Аналогично ищется и максимальный элемент. Для этого нужно следовать правым указателям.
'''Node''' minimum(x : '''Node'''):
'''if''' x.left == ''null''
'''return''' x
'''return''' minimum(x.left)

'''Node''' maximum(x : '''Node'''):
'''if''' x.right == ''null''
'''return''' x
'''return''' maximum(x.right)
Данные функции принимают корень поддерева, и возвращают минимальный (максимальный) элемент в поддереве. Обе процедуры выполняются за время <tex>O(h)</tex>.

=== Поиск следующего и предыдущего элемента ===
====Реализация с использованием информации о родителе====
Если у узла есть правое поддерево, то следующий за ним элемент будет минимальным элементом в этом поддереве. Если у него нет правого поддерева, то нужно следовать вверх, пока не встретим узел, который является левым дочерним узлом своего родителя. Поиск предыдущего выполнятся аналогично. Если у узла есть левое поддерево, то следующий за ним элемент будет максимальным элементом в этом поддереве. Если у него нет левого поддерева, то нужно следовать вверх, пока не встретим узел, который является правым дочерним узлом своего родителя.
'''Node''' next(x : '''Node'''):
'''if''' x.right != ''null''
'''return''' minimum(x.right)
y = x.parent
'''while''' y != ''null'' '''and''' x == y.right
x = y
y = y.parent
'''return''' y

'''Node''' prev(x : '''Node'''):
'''if''' x.left != ''null''
'''return''' maximum(x.left)
y = x.parent
'''while''' y != ''null'' '''and''' x == y.left
x = y
y = y.parent
'''return''' y
Обе операции выполняются за время <tex>O(h)</tex>.
====Реализация без использования информации о родителе====
Рассмотрим поиск следующего элемента для некоторого ключа <tex>x</tex>. Поиск будем начинать с корня дерева, храня текущий узел <tex>current</tex> и узел <tex>successor</tex>, последний посещенный узел, ключ которого больше <tex>x</tex>. 
Спускаемся вниз по дереву, как в алгоритме поиска узла. Рассмотрим ключ текущего узла <tex>current</tex>. Если <tex>current.key \leqslant x</tex>, значит следующий за <tex>x</tex> узел находится в правом поддереве (в левом поддереве все ключи меньше <tex>current.key</tex>). Если же <tex>x < current.key</tex>, то <tex>x < next(x) \leqslant current.key</tex>, поэтому <tex>current</tex> может быть следующим для ключа <tex>x</tex>, либо следующий узел содержится в левом поддереве <tex>current</tex>. Перейдем к нужному поддереву и повторим те же самые действия. 
Аналогично реализуется операция поиска предыдущего элемента.
'''Node''' next(x : '''T'''):
'''Node''' current = root, successor = ''null'' // root {{---}} корень дерева
'''while''' current != ''null''
'''if''' current.key > x
successor = current
current = current.left
'''else'''
current = current.right
'''return''' successor
=== Вставка ===
Операция вставки работает аналогично поиску элемента, только при обнаружении у элемента отсутствия ребенка нужно подвесить на него вставляемый элемент.
====Реализация с использованием информации о родителе====
'''func''' insert(x : '''Node''', z : '''Node'''): // x {{---}} корень поддерева, z {{---}} вставляемый элемент
'''while''' x != ''null''
'''if''' z.key > x.key
'''if''' x.right != ''null''
x = x.right
'''else'''
z.parent = x
x.right = z
'''break'''
'''else if''' z.key < x.key
'''if''' x.left != ''null''
x = x.left
'''else'''
z.parent = x
x.left = z
'''break'''
====Реализация без использования информации о родителе====
'''Node''' insert(x : '''Node''', z : '''T'''): // x {{---}} корень поддерева, z {{---}} вставляемый ключ
'''if''' x == ''null''
'''return''' Node(z) // подвесим Node с key = z
'''else if''' z < x.key
x.left = insert(x.left, z)
'''else if''' z > x.key
x.right = insert(x.right, z)
'''return''' x

Время работы алгоритма для обеих реализаций {{---}} <tex>O(h)</tex>.

=== Удаление ===
====Нерекурсивная реализация====
Для удаления узла из бинарного дерева поиска нужно рассмотреть три возможные ситуации. Если у узла нет дочерних узлов, то у его родителя нужно просто заменить указатель на <tex>null</tex>. Если у узла есть только один дочерний узел, то нужно создать новую связь между родителем удаляемого узла и его дочерним узлом. Наконец, если у узла два дочерних узла, то нужно найти следующий за ним элемент (у этого элемента не будет левого потомка), его правого потомка подвесить на место найденного элемента, а удаляемый узел заменить найденным узлом. Таким образом, свойство бинарного дерева поиска не будет нарушено. Данная реализация удаления не увеличивает высоту дерева. Время работы алгоритма {{---}} <tex>O(h)</tex>.
{| border="1" cellpadding="5" cellspacing="0"
!Случай
!Иллюстрация
|-
|'''Удаление листа'''
| [[Файл:Bst_del1.png |581px]]
|-
|'''Удаление узла с одним дочерним узлом'''
| [[Файл:Bst_del2.png |604px]]
|-
|'''Удаление узла с двумя дочерними узлами'''
| [[Файл:Bst_del3.png‎|900px]]
|}
'''func''' delete(t : '''Node''', v : '''Node'''): // <tex>t</tex> {{---}} дерево, <tex>v</tex> {{---}} удаляемый элемент
p = v.parent // предок удаляемого элемента
'''if''' v.left == ''null'' '''and''' v.right == ''null'' // первый случай: удаляемый элемент - лист
'''if''' p.left == v
p.left = ''null''
'''if''' p.right == v
p.right = ''null''
'''else if''' v.left == ''null'' '''or''' v.right == ''null'' // второй случай: удаляемый элемент имеет одного потомка
'''if''' v.left == ''null''
'''if''' p.left == v
p.left = v.right
'''else'''
p.right = v.right
v.right.parent = p
'''else'''
'''if''' p.left == v
p.left = v.left
'''else'''
p.right = v.left
v.left.parent = p
'''else''' // третий случай: удаляемый элемент имеет двух потомков
successor = next(v, t)
v.key = successor.key
'''if''' successor.parent.left == successor
successor.parent.left = successor.right
'''if''' successor.right != ''null''
successor.right.parent = successor.parent
'''else'''
successor.parent.right = successor.left
'''if''' successor.left != ''null''
successor.right.parent = successor.parent

====Рекурсивная реализация====
При рекурсивном удалении узла из бинарного дерева нужно рассмотреть три случая: удаляемый элемент находится в левом поддереве текущего поддерева, удаляемый элемент находится в правом поддереве или удаляемый элемент находится в корне. В двух первых случаях нужно рекурсивно удалить элемент из нужного поддерева. Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла, то нужно заменить его минимальным элементом из правого поддерева и рекурсивно удалить '''этот''' минимальный элемент из правого поддерева. Иначе, если удаляемый элемент имеет один дочерний узел, нужно заменить его потомком. Время работы алгоритма {{---}} <tex>O(h)</tex>.
Рекурсивная функция, возвращающая дерево с удаленным элементом <tex>z</tex>:
'''Node''' delete(root : '''Node''', z : '''T'''): // корень поддерева, удаляемый ключ
'''if''' root == ''null''
'''return''' root
'''if''' z < root.key
root.left = delete(root.left, z)
'''else if''' z > root.key
root.right = delete(root.right, z)
'''else if''' root.left != ''null'' '''and''' root.right != ''null''
root.key = minimum(root.right).key
root.right = delete(root.right, root.key)
'''else'''
'''if''' root.left != ''null''
root = root.left
'''else'''
root = root.right
'''return''' root

==Задачи о бинарном дереве поиска==

===Проверка того, что заданное дерево является деревом поиска===

{{Задача
|definition = Определить, является ли заданное двоичное дерево деревом поиска.
}}
[[Файл:Not_Enough.png|right|thumb|291px|Пример дерева, для которого недостаточно проверки лишь его соседних вершин]]
Для того чтобы решить эту задачу, применим [[Обход в глубину, цвета вершин|обход в глубину]]. Запустим от корня рекурсивную логическую функцию, которая выведет <tex>\mathtt{true}</tex>, если дерево является BST и <tex>\mathtt{false}</tex> в противном случае. Чтобы дерево не являлось BST, в нём должна быть хотя бы одна вершина, которая не попадает под определение дерева поиска. То есть достаточно найти всего одну такую вершину, чтобы выйти из рекурсии и вернуть значение <tex>\mathtt{false}</tex>. Если же, дойдя до листьев, функция не встретит на своём пути такие вершины, она вернёт значение <tex>\mathtt{true}</tex>.

Функция принимает на вход исследуемую вершину, а также два значения: <tex>\mathtt{min}</tex> и <tex>\mathtt{max}</tex>, которые до вызова функции равнялись <tex> \infty </tex> и <tex> -\infty </tex> соответственно, где <tex> \infty </tex> — очень большое число, т.е. ни один ключ дерева не превосходит его по модулю. Казалось бы, два последних параметра не нужны. Но без них программа может выдать неверный ответ, так как сравнения только вершины и её детей недостаточно. Необходимо также помнить, в каком поддереве для более старших предков мы находимся. Например, в этом дереве вершина с номером <tex>8</tex> находится левее вершины, в которой лежит <tex>5</tex>, чего не должно быть в дереве поиска, однако после проверки функция бы вернула <tex>\mathtt{true}</tex>.

'''bool''' isBinarySearchTree(root: '''Node'''): // Здесь root — корень заданного двоичного дерева.

'''bool''' check(v : '''Node''', min: '''T''', max: '''T'''): // min и max — минимально и максимально допустимые значения в вершинах поддерева.
'''if''' v == ''null'' '''return''' ''true''
'''if''' v.key <= min '''or''' max <= v.key '''return''' ''false''
'''return''' check(v.left, min, v.key) '''and''' check(v.right, v.key, max)

'''return''' check(root, <tex> -\infty </tex>, <tex> \infty </tex>)

Время работы алгоритма {{---}} <tex>O(n)</tex>, где <tex>n</tex> {{---}} количество вершин в дереве.

===Задачи на поиск максимального BST в заданном двоичном дереве===

{{Задача
|definition = Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин.
}}
Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:
* Значение в вершине больше максимума в её левом поддереве;
* Значение в вершине меньше минимума в её правом поддереве;
* Левое и правое поддерево являются деревьями поиска.

Введём <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>, которые будут хранить минимум в левом поддереве вершины и максимум в правом. Тогда мы должны будем проверить, являются ли эти поддеревья деревьями поиска и, если да, лежит ли ключ вершины <tex>\mathtt{v}</tex> между этими значениями <tex>\mathtt{v.min}</tex> и <tex>\mathtt{v.max}</tex>. Если вершина является листом, она автоматически становится деревом поиска, а её ключ {{---}} минимумом или максимумом для её родителя (в зависимости от расположения вершины). Функция <tex>\mathtt{cnt}</tex> записывает в <tex>\mathtt{v.kol}</tex> количество вершин в дереве, если оно является деревом поиска или <tex>\mathtt{-1}</tex> в противном случае. После выполнения функции ищем за линейное время вершину с наибольшим значением <tex>\mathtt{v.kol}</tex>.

'''int''' count(root: '''Node'''): // root — корень заданного двоичного дерева.

'''int''' cnt(v: '''Node'''):
'''if''' v == ''null''
v.kol = 0
'''return''' = 0
'''if''' cnt(v.left) != -1 '''and''' cnt(v.right) != -1
'''if''' v.left == ''null'' '''and''' v.right == ''null''
v.min = v.key
v.max = v.key
v.kol = 1
'''return''' 1
'''if''' v.left == ''null''
'''if''' v.right.max > v.key
v.min = v.key
v.kol = cnt(v.right) + 1
'''return''' v.kol
'''if''' v.right == ''null''
'''if''' v.left.min < v.key
v.max = v.key
v.kol = cnt(v.left) + 1
'''return''' v.kol
'''if''' v.left.min < v.key '''and''' v.right.max > v.key
v.min = v.left.min
v.max = v.right.max
v.kol = v.left.kol + v.right.kol + 1
v.kol = cnt(v.left) + cnt(v.right) + 1
'''return''' v.kol
'''return''' -1

'''return''' cnt(root)

Алгоритм работает за <tex>O(n)</tex>, так как мы прошлись по дереву два раза за время, равное количеству вершин.

===Восстановление дерева по результату обхода preorderTraversal===

{{Задача
|definition = Восстановить дерево по последовательности, выведенной после выполнения процедуры <tex>\mathrm{preorderTraversal}</tex>.
}}
[[Файл:BST_from_seq.gif|right|thumb|257px|Восстановление дерева поиска по последовательности ключей]]

Как мы помним, процедура <tex>\mathrm{preorderTraversal}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына. Когда мы, желая найти такую вершину, встречаем какую-нибудь другую, уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет. Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет обновляться каждый раз, когда появится новый максимум.

Процедура восстановления дерева работает за <tex>O(n)</tex>.

Разберём алгоритм на примере последовательности <tex>\mathtt{8}</tex> <tex>\mathtt{2}</tex> <tex>\mathtt{1}</tex> <tex>\mathtt{4}</tex> <tex>\mathtt{3}</tex> <tex>\mathtt{5}</tex>.

Будем выделять красным цветом вершины, рассматриваемые на каждом шаге, чёрным жирным {{---}} их родителей, курсивом {{---}} убывающие подпоследовательности (в случаях, когда мы их рассматриваем) или претендентов на добавление к ним правого ребёнка (когда рассматривается вершина, нарушающая убывающую последовательность).
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Состояние
последовательности
!style="background-color:#EEE"| Действие
!style="background-color:#EEE"| Пояснение
|-
|style="background-color:#FFF;padding:2px 10px"| '''8''' 2 1 4 3 5
|style="background-color:#FFF;padding:2px 10px"| Делаем вершину корнем.
|style="background-color:#FFF;padding:2px 10px"| ''Первая вершина всегда будет корнем, так как вывод начинался с него.''
|-
|style="background-color:#FFF;padding:2px 10px"| '''''8''''' '''''2''''' ''1'' 4 3 5
|rowspan=2 style="background-color:#FFF;padding:2px 10px"|Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына.
|rowspan=2 style="background-color:#FFF;padding:2px 10px"| ''Каждая последующая вершина становится левым сыном предыдущей, так как выводя ключи, мы двигались по дереву поиска влево, пока есть вершины.''
|-
| style="background-color:#FFF;padding:2px 10px"| ''8 '''2''''' '''''1''''' 4 3 5
|-
|style="background-color:#FFF;padding:2px 10px"| ''8 '''2''''' 1 '''4''' 3 5
|style="background-color:#FFF;padding:2px 10px"| Для вершины, нарушившей убывающую последовательность, ищем максимальное значение, меньшее его. В данном случае оно равно <tex>\mathtt{2}</tex>. Затем добавляем вершину.
|style="background-color:#FFF;padding:2px 10px"| ''На моменте вывода следующего номера процедура обратилась уже к какому-то из правых поддеревьев, так как влево идти уже некуда. Значит, нам необходимо найти узел, для которого данная вершина являлась бы правым сыном. Очевидно, что в её родителе не может лежать значение, которое больше её ключа. Но эту вершину нельзя подвесить и к меньшим, иначе нашёлся бы более старший предок, также хранящий какое-то значение, которое меньше, чем в исследуемой. Для этого предка вершина бы попала в левое поддерево. И тогда возникает противоречие с определением дерева поиска. Отсюда следует, что родитель определяется единственным образом {{---}} он хранит максимум среди ключей, не превосходящих значения в подвешиваемой вершине, что и требовалось доказать.''
|-
|style="background-color:#FFF;padding:2px 10px"| 8 2 1 '''''4''''' '''''3''''' 5
|style="background-color:#FFF;padding:2px 10px"| Находим убывающую подпоследовательность. Каждую вершину подвешиваем к последней из взятых ранее в качестве левого сына.
|style="background-color:#FFF;padding:2px 10px"| ''Зайдя в правое поддерево, процедура обхода снова до упора начала двигаться влево, поэтому действуем аналогичным образом.''
|-
|style="background-color:#FFF;padding:2px 10px"| ''8'' 2 1 '''''4''''' 3 '''5'''
|style="background-color:#FFF;padding:2px 10px"| Для этой вершины ищем максимальное значение, меньшее его. Затем добавляем вершину.
|style="background-color:#FFF;padding:2px 10px"| ''Здесь процедура снова обратилась к правому поддереву. Рассуждения аналогичны. Ключ родителя этой вершины равен <tex>\mathtt{4}</tex>.''
|}

==См. также==
* [[Поисковые структуры данных]]
* [[Рандомизированное бинарное дерево поиска]]
* [[Красно-черное дерево]]
* [[АВЛ-дерево]]

==Источники информации==
* [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0 Википедия {{---}} Двоичное дерево поиска]
* [https://en.wikipedia.org/wiki/Binary_search_tree Wikipedia {{---}} Binary search tree]
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

[[Категория: Деревья поиска]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]

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

2019-01-06T14:04:27Z

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

==Определение==
{{Определение
|definition=
'''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:

* Значение в любой вершине не меньше (если куча для максимума), чем значения её потомков.
* На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
* Последний слой заполнен слева направо (как показано на рисунке)
}}
[[Файл:Min_heap.png‎|thumb|325px|Пример кучи для минимума]]
[[Файл:Min_heap_array.png‎|thumb|325px|Хранение кучи в массиве, красная стрелка {{---}} левый сын, зеленая {{---}} правый]]
Удобнее всего двоичную кучу хранить в виде массива <tex>a[0..n-1]</tex>, у которого нулевой элемент, <tex>a[0]</tex> — элемент в корне, а потомками элемента <tex>a[i]</tex> являются <tex>a[2i+1]</tex> и <tex>a[2i+2]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{n})</tex>, где <tex>n</tex> — количество узлов дерева.

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

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

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

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

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
и <tex> \mathrm {siftUp} </tex> (просеивание вверх).

====siftDown====
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.

Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
Процедура выполняется за время <tex>O(\log{n})</tex>.

<code style="display:inline-block">
'''function''' siftDown(i : '''int'''):
'''while''' 2 * i + 1 < a.heapSize // heapSize {{---}} количество элементов в куче
left = 2 * i + 1 // left {{---}} левый сын
right = 2 * i + 2 // right {{---}} правый сын
j = left
'''if''' right < a.heapSize '''and''' a[right] < a[left]
j = right
'''if''' a[i] <= a[j]
'''break'''
swap(a[i], a[j])
i = j
</code>

====siftUp====
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>
для этого отца. Иными словами, слишком маленький элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{n})</tex>.
<code style="display:inline-block">
'''function''' siftUp(i : '''int'''):
'''while''' a[i] < a[(i - 1) / 2] // i <tex>==</tex> 0 {{---}} мы в корне
swap(a[i], a[(i - 1) / 2])
i = (i - 1) / 2
</code>

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

Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{n})</tex>.
Извлечение выполняется в четыре этапа:
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается <math> \mathrm {siftDown} </math> для корня.
# Сохранённый элемент возвращается.

<code style="display:inline-block">
'''int''' extractMin():
'''int''' min = a[0]
a[0] = a[a.heapSize - 1]
a.heapSize = a.heapSize - 1
siftDown(0)
'''return''' min
</code>

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

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

<code style="display:inline-block">
'''function''' insert(key : '''int'''):
a.heapSize = a.heapSize + 1
a[a.heapSize - 1] = key
siftUp(a.heapSize - 1)
</code>

===Построение кучи за O(n) ===
{{Определение | definition =
'''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>d</tex> потомков.
}}

Дан массив <tex>a[0.. n - 1].</tex> Требуется построить <tex>d</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива {{---}} сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента <math>\mathrm {siftUp}</math>. Временная оценка такого алгоритма <tex> O(n\log{n})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(n) </tex>.

Представим, что в массиве хранится дерево (<tex>a[0] - </tex> корень, а потомками элемента <tex>a[i]</tex> являются <tex>a[di+1]...a[di+d]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка: от <tex dpi=140>\dfrac{n}{d}</tex> до <tex>0</tex>,{{---}} так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.
{{Лемма
|statement= На выходе получим искомую кучу.
|proof= При вызове <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами. После выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
}}
{{Лемма
|statement= Время работы этого алгоритма <tex> O(n) </tex>.
|proof= Число вершин на высоте <tex>h</tex> в куче из <tex>n</tex> элементов не превосходит <tex dpi = "160"> \left \lceil \frac{n}{d^h} \right \rceil </tex>. Высота кучи не превосходит <tex> \log_{d}n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит

<tex dpi = "160"> \sum_{h = 1}^H \limits\frac{n}{d^h} \cdot d </tex> <tex dpi = "150"> \cdot h </tex> <tex dpi = "160"> = n \cdot d \cdot {\sum_{h = 1}^H \limits}\frac{h}{d^h}. </tex>

Докажем вспомогательную лемму о сумме ряда.

{{Лемма
|statement= <tex dpi = "160"> {\sum_{h = 1}^\infty \limits}\frac{h}{d^h} = \frac{d}{(d - 1)^2} . </tex>
|proof=
Обозначим за <tex>s</tex> сумму ряда. Заметим, что
<tex dpi = "160"> \frac{n}{d^n} = \frac{1}{d} \cdot \frac{n - 1}{d ^{n - 1}} + \frac{1}{d^n}. </tex>

<tex dpi = "160">{\sum_{n = 1}^\infty \limits}\frac{1}{d^n}</tex> {{---}} это сумма бесконечной убывающей геометрической прогрессии, и она равна <tex dpi = "160">
\frac{\frac{1}{d}}{1 - \frac{1}{d}} = \frac{1}{d - 1}. </tex>

Получаем <tex>s</tex> <tex dpi = "160" >=\frac{1}{d}</tex> <tex>\cdot s +</tex> <tex dpi = "160" > \frac{1}{d - 1}. </tex> Откуда <tex>s</tex> <tex dpi = "160"> = \frac{d}{(d - 1)^2}. </tex>
}}

Подставляя в нашу формулу результат леммы, получаем <tex >n</tex> <tex dpi = "160">\cdot (\frac {d}{d - 1})^2 </tex> <tex> \leqslant 4 \cdot n </tex> <tex>=O(n).</tex>
}}

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

===Слияние двух куч===
Даны две кучи <tex>a</tex> и <tex>b</tex>, размерами <tex>n</tex> и <tex>m</tex>, требуется объединить эти две кучи.
====Наивная реализация====
Поочередно добавим все элементы из <tex>b</tex> в <tex>a</tex>. Время работы {{---}} <tex>O(m \log(n+m))</tex>.
<code style="display:inline-block">
'''function''' merge(a, b : '''Heap'''):
'''while''' b.heapSize > 0
a.insert(b.extractMin())
</code>

====Реализация с помощью построения кучи====
Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(n + m)</tex>.

<code style="display:inline-block">
'''function''' merge(a, b : '''Heap'''):
'''for''' i = 0 '''to''' b.heapSize - 1
a.heapSize = a.heapSize + 1
a[a.heapSize - 1] = b[i]
a.heapify()
</code>

===Поиск k-ого элемента===
Требуется найти <tex>k</tex>-ый по величине элемент в куче.

# Создаем новую кучу, в которой будем хранить пару <tex>\langle \mathtt{value}, \mathtt{index} \rangle</tex>, где <tex>\mathtt{value}</tex> {{---}} значение элемента, а <tex>\mathtt{index}</tex> {{---}} индекс элемента в основном массиве, и добавляем в нее корень кучи.
# Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <tex>k - 1</tex> раз.
# В корне новой кучи будет находиться ответ.

Время работы алгоритма {{---}} <tex>O(k \log k)</tex>.

При <tex>n \lessapprox k \log k </tex> выгоднее запускать [[поиск k-ой порядковой статистики]].
[[Файл:Min_heap_kth.png‎|thumb|center|650px|Пример при <tex>k = 5</tex>, красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]

== См. также ==
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]
* [[Левосторонняя куча]]

== Источники информации ==
* [[wikipedia:ru:Двоичная куча|Википедия {{---}} Двоичная куча]]
* [[wikipedia:ru:Очередь с приоритетом|Википедия {{---}} Очередь с приоритетом]]
* [[wikipedia:en:Binary heap|Wikipedia {{---}} Binary heap]]
* [[wikipedia:en:Priority queue|Wikipedia {{---}} Priority queue]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]