2.4.3 Построение кучи

Пусть дан массив A[1..n], который требуется превратить в кучу, переста­вив его элементы. Для этого можно использовать процедуру Heapify, приме­няя её по очереди ко всем вершинам, начиная с нижних. Поскольку вершины с номерами ,...,n являются листьями, поддеревья с этими вершинами удовлетворяют основному свойству. Для каждой из оставшихся вершин, в поряд­ке убывания индексов, мы применяем процедуру Heapify. Порядок обработки вершин гарантирует, что каждый раз условия вызова процедуры (выполнение основного свойства для поддеревьев) будут выполнены.

Листинг 2.5 – Процедура построения кучи

Ясно, что время работы процедуры Build-Heap не превышает O(nlog n). Действительно, процедура Heapify вызывается О(п) раз, а каждое её выпол­нение требует времени O(log n). Однако, эту оценку можно улучшить.

Итак, куча строится за линейное время, восстановление основного свойства кучи происходит за время, пропорциональное высоте дерева, т.е. log n, всего же сортируется

n - элементов, поэтому общее время есть O(nlog n).