Пронумеруем все строки алгоритма и структурируем его.

(1)voiddownHeap(int a[], long k, long n)

(2){

(3)  intnew_elem;

(4)  long child;

(5)  new_elem = a[k];

(6)  while(k <= n/2)

(7)  {           

(8)    child = 2*k;

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

(10)    child++;

(11)    if(new_elem>= a[child] )

(12)      break;

(13)    a[k] = a[child];    

(14)    k = child;

(15)  }

(16)  a[k] = new_elem;

(17)}

(18)voidheapSort(int a[], long size)

(19){

(20)  long i;

(21)  int temp;

(22)  for(i=size/2-1; i >= 0; i--)

(23)    downHeap(a, i, size-1);

(24)  for(i=size-1; i > 0; i--)

(25)  {

(26)    temp=a[i];

(27)    a[i]=a[0];

(28)    a[0]=temp;

(29)downHeap(a, 0, i);

(30)  }

(31)}

 

Рассматриваемый исходный код представляет собой реализацию алгоритма пирамидальной сортировки.

 Алгоритм на первом этапе строит пирамиду, которая имеет следующую структуру. На верху пирамиды находится один элемент. У каждого элемента есть два потомка, которые меньше или равны родителя. Каждая цепочка от вершины до основания имеет длину m или m+1. Построенная пирамида укладывается в массив. Для элемента массива с номеромi потомки имеют индексы 2i+1 и 2i+2, а родитель – целая часть от деление iпополам.

На втором этапе алгоритм заменяет вершину пирамиды (максимальный элемент) на последний элемент в массиве. Далее на всех элементах пирамиды кроме последнего происходит построение пирамиды (первый этап). Затем заменяется вершина вновь построенной пирамиды на второй элемент с конца. Количество таких повторений равно количеству элементов в массиве.

Заметим, что в строке 29 после замены вершины пирамиды на очередной правый элемент происходит перестроение пирамиды с использованием замененного элемента i, что не верно. На некотором шаге получиться ситуацию, когда при применении функции downHeapi-ый элемент переместится в вершину пирамиды, что нарушит сортировку. Для правильной работы алгоритма необходимо перестроить пирамиду для элементов от 0 до i-1.

Правильная реализация с комментариями представлена ниже.

 

(1)voiddownHeap(int a[], long k, long n)

(2){

   //  процедура просеивания следующего элемента

   //  До процедуры: a[k+1]...a[n]  - пирамида

//  После:  a[k]...a[n]  - пирамида

(3)  intnew_elem;

(4)  long child;

(5)  new_elem = a[k];

    // пока у a[k] есть дети

(6)  while(k <= n/2)

(7)  {           

(8)    child = 2*k;

       //  выбираем большего сына

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

(10)    child++;

(11)    if(new_elem>= a[child] )

(12)      break;

        // переносим сына наверх

(13)    a[k] = a[child];    

(14)    k = child;

(15)  }

(16)  a[k] = new_elem;

(17)}

(18)voidheapSort(int a[], long size)

(19){

(20)  long i;

(21)  int temp;

      // строим пирамиду

(22)  for(i=size/2-1; i >= 0; i--)

(23)    downHeap(a, i, size-1);

     // теперьa[0]...a[size-1] пирамида

(24)  for(i=size-1; i > 0; i--)

(25)  {

        // меняем первый с последним

(26)    temp=a[i];

(27)    a[i]=a[0];

(28)    a[0]=temp;

        // восстанавливаем пирамидальность a[0]...a[i-1]

(29)downHeap(a, 0, i-1);

(30)  }

(31)}

(1)voiddownHeap(int a[], long k, long n)

(2){

   //  процедура просеивания следующего элемента

   //  До процедуры: a[k+1]...a[n]  - пирамида

//  После:  a[k]...a[n]  - пирамида

(3)  intnew_elem;

(4)  long child;

(5)  new_elem = a[k];

    // пока у a[k] есть дети

(6)  while(k <= n/2)

(7)  {           

(8)    child = 2*k;

       //  выбираем большего сына

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

(10)    child++;

(11)    if(new_elem>= a[child] )

(12)      break;

        // переносим сына наверх

(13)    a[k] = a[child];    

(14)    k = child;

(15)  }

(16)  a[k] = new_elem;

(17)}

(18)voidheapSort(int a[], long size)

(19){

(20)  long i;

(21)  int temp;

      // строим пирамиду

(22)  for(i=size/2-1; i >= 0; i--)

(23)    downHeap(a, i, size-1);

     // теперьa[0]...a[size-1] пирамида

(24)  for(i=size-1; i > 0; i--)

(25)  {

        // меняем первый с последним

(26)    temp=a[i];

(27)    a[i]=a[0];

(28)    a[0]=temp;

        // восстанавливаем пирамидальность a[0]...a[i-1]

(29)downHeap(a, 0, i-1);

(30)  }

(31)}