Изменения

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры sift_down <math> \mathrm {siftDown} </math> (просеивание вниз)и sift_up <math> \mathrm {siftUp} </math> (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией sift_down(i)<math> \mathrm {siftDown} </math>.Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем sift_down() <math> \mathrm {siftDown} </math> для этого сына.

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

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем sift_up<math> \mathrm {siftUp} </math>

# Вызывается sift_down(i) <math> \mathrm {siftDown} </math> для корня.

<code> extract_min'''function''' extractMin(): min = A[0] A[0] = A[A.heap_size - 1] A.heap_size = A.heap_size - 1 sift_down siftDown(0) '''return ''' min</code>

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

<code> '''function''' insert(key): A.heap_size = A.heap_size + 1 A[A.heap_size - 1] = key sift_up siftUp(A.heap_size - 1)</code>

Дан массив <tex>A[0.. N - 1].</tex> Требуется построить <tex>D</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива - по очереди добавить все его элементы (сделать sift_down <math> \mathrm {siftDown} </math> для каждого). Временная оценка такого алгоритма <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>). Сделаем sift_down <math> \mathrm {siftDown} </math> для вершин, имеющих хотя бы одного потомка, начиная с конца(от <tex> n - 1</tex> до <tex>0</tex>) (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).

|proof= При вызове sift_down <math> \mathrm {siftDown} </math> для вершины, ее поддерево является кучей, после выполнения sift_down <math> \mathrm {siftDown} </math> поддерево с этой вершиной будет являться кучей. Значит после выполнения всех sift_down <math> \mathrm {siftDown} </math> получится куча.