Изменения

===Построение кучи за O(n) ===

<code style="display:inline-block"> '''function''' heapify(): '''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 <tex>\neq</tex> 0 a.insert(b.extractMin())</code> ====Реализация с помощью построения кучи====Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(a.heapSize n + b.heapSizem)</tex>.

'''function''' merge(a, b : '''heapHeap'''):

===Поиск k-ого элемента===

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