333
правки
Изменения
→Восстановление свойств кучи
===Восстановление свойств кучи===
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <mathtex>\mathrm {siftDown}</mathtex> (просеивание вниз)и <mathtex>\mathrm {siftUp}</mathtex> (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <mathtex>\mathrm {siftDown}</mathtex>.Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <mathtex>\mathrm {siftDown}</mathtex> для этого сына.
Процедура выполняется за время <tex>O(\log{N})</tex>.
<code>
'''function''' siftDown('''int''' i):
'''if''' 2 * i + 1 <= A.heap_size <font color = "green">// <tex> heap</tex>_<tex>size </tex> {{---}} количество элементов в куче</font>
left = A[2 * i + 1] <font color = "green">// левый сын</font>
'''else'''
left = inf
'''if''' 2 * i + 2 <= A.heap_size
right = A[2 * i + 2] <font color = "green">// правый сын</font>
'''else'''
right = inf
'''if''' left == right == inf '''return'''
'''if''' right <= left && right < A[i]
swap(A[2 * i + 2], A[i])
siftDown(2 * i + 2)
'''if''' (left < A[i])
swap(A[2 * i + 1], A[i])
siftDown(2 * i + 1)
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.
для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{N})</tex>.
<code> '''function''' siftUp('''int''' i):
'''if''' i == 0
'''return''' <font color = "green">//Мы мы в корне</font>
'''if''' A[i] < A[i / 2]
swap(A[i], A[i / 2])
siftUp(i / 2)
</code>
===Извлечение минимального элемента===
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается <mathtex>\mathrm {siftDown}</mathtex> для корня.
# Сохранённый элемент возвращается.
Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <mathtex>\mathrm {siftUp}</mathtex>.
'''function''' insert(key):
}}
Дан массив <tex>A[0.. N - 1].</tex> Требуется построить <tex>D</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива - по очереди добавить все его элементы (сделать <mathtex>\mathrm {siftDown}</mathtex> для каждого). Временная оценка такого алгоритма <tex> O(N\log{N})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(N) </tex>. Представим, что в массиве хранится дерево (<tex>A[0] - </tex> корень, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i+1]...A[2i+D]</tex>). Сделаем <mathtex>\mathrm {siftDown}</mathtex> для вершин, имеющих хотя бы одного потомка, начиная с конца(от <tex> n - 1</tex> до <tex>0</tex>) (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).
{{Лемма
|statement= На выходе получим искомую кучу.
|proof= При вызове <mathtex>\mathrm {siftDown}</mathtex> для вершины, ее поддерево является кучей, после выполнения <mathtex>\mathrm {siftDown}</mathtex> поддерево с этой вершиной будет являться кучей. Значит после выполнения всех <mathtex>\mathrm {siftDown}</mathtex> получится куча.
}}
{{Лемма
