for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1)

public void downHeap(int a[], int k, int n)

{

int new_elem; int child; new_elem = a[k]; while(k <= n/2)

{

child = 2*k;

if( child < n && a[child] < a[child+1] ) child++;

if( new_elem >= a[child] ) break; a[k] = a[child];

k = child }

a[k] = new_elem;

}

Отчитайки височината на пирамидата h <= log n, downHeap() изисква O(log n) време.
И така, задачата за построяване на пирамидата от масива е успешно решена. Както се вижда от свойството на пирамидата в корена и винаги се намира най-големия елемент. От тук се ражда и идеята за фаза 2 на алгоритъма.

1. 
   Взимаме най-горния елемент на пиирамидата a[0]...a[n] (първият в масива) и го разменяме с последния. Сега забравяме за този елемент и по-нататък разглеждаме массива a[0]...a[n-1]. За превръщането му в пирамида е достатъчо да се пресее само новия елемент.
   
2. 
   Повтаряме стъпка 1, докато обработваната част от масива не намалее до 1 елемент.
   

Очевидно в края на масива всеки път ще попада най-големия елемент от текущата пирамида, затова в дясната част постепенно възниква подредена последователност.

22. Списъци.Типове и реализация (през шаблон и обекти). Приложни аспекти.

Най–често срещаните и използвани са линейните (списъчни) структури. Те представляват абстракция на всякакви видове редици, последователности, поредици и други подобни от реалния свят. Списък е линейна структура от данни, която съдържа поредица от елементи. Списъкът има свойството дължина (брой елементи) и елементите му са наредени последователно.
Списъкът позволява добавяне на елементи на всяко едно място, премахването им и последователното им обхождането. Както споменахме по-горе, един АТД може да има няколко реализации.