#include "PyramidSort.h"
 
PyramidSort::PyramidSort(int n, int* x) : Sort(n, x) {
    this->algName = "Pyramid Sort";
}
 
void PyramidSort::Screening(int k, int end) {
 
    /* Это чтобы при k=0 и n=0 не делалось лишней
       перестановки*/
    if (0 == end) return;
 
    int tmp;
    int childPos;
    tmp = this->x[k];
 
    while (k <= end/2) {
        childPos = 2*k;  // Левый ребенок элемента k
 
        /* выбираем большего ребенка элемента k
           из 2-х: либо левый, либо правый
           */        
        if (childPos < end && this->x[childPos] < this->x[childPos + 1]) {
            childPos++;
        }
        /* Если родитель x[k] больше всех своих детей,
           то ничего не делаем, он стоит на правильном месте */
        if(tmp >= this->x[childPos]) break;
 
        // иначе - меняем x[k] с наибольшим ребенком
        this->x[k] = this->x[childPos];
        k = childPos;
        this->CountSwap();
    }
    this->x[k] = tmp; this->CountSwap();
}
 
void PyramidSort::Run(void) {
    int i;
    int tmp;
 
    // Построение пирамиды 
    for (i = this->n/2; i >= 0; i--) {
      this->Screening(i, (this->n - 1));
    }
 
    /* Формирование конечной отсортированной
       последовательности + "балансирование"
       пирамиды */
    for (i = this->n - 1; i > 0; i--) {
        // меняем первый с последним 
        this->Swap(0, i);
 
        /* Восстановление баланса 
           для пирамиды x[0..i-1] */
        this->Screening(0, i-1);
    }
}
 
PyramidSort::~PyramidSort(void)
{
}