333
правки
Изменения
Нет описания правки
===Восстановление свойств кучи===
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <texmath> \mathrm {siftDown} </texmath> (просеивание вниз)и <texmath> \mathrm {siftUp} </texmath> (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <texmath> \mathrm {siftDown} </texmath>.Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <texmath> \mathrm {siftDown} </texmath> для этого сына.
Процедура выполняется за время <tex>O(\log{N})</tex>.
siftDown(2 * i + 1)
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <texmath> \mathrm {siftUp} </texmath>.
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <texmath> \mathrm {siftUp} </texmath>
для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{N})</tex>.
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается <texmath> \mathrm {siftDown} </texmath> для корня.
# Сохранённый элемент возвращается.
Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <texmath> \mathrm {siftUp} </texmath>.
'''function''' insert(key):
}}
Дан массив <tex>A[0.. N - 1].</tex> Требуется построить <tex>D</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива - по очереди добавить все его элементы (сделать <texmath> \mathrm {siftDown} </texmath> для каждого). Временная оценка такого алгоритма <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>). Сделаем <texmath> \mathrm {siftDown} </texmath> для вершин, имеющих хотя бы одного потомка, начиная с конца(от <tex> n - 1</tex> до <tex>0</tex>) (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).
{{Лемма
|statement= На выходе получим искомую кучу.
|proof= При вызове <texmath> \mathrm {siftDown} </texmath> для вершины, ее поддерево является кучей, после выполнения <texmath> \mathrm {siftDown} </texmath> поддерево с этой вершиной будет являться кучей. Значит после выполнения всех <texmath> \mathrm {siftDown} </texmath> получится куча.
}}
{{Лемма
