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

Пусть дан массив 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).