/* Функция "балансировки" пирамиды.
   (просеивания, добавления элементов) */
template<class T>
void Screening(T* x, int k, int n) {
    /* Это чтобы при k=0 и n=0 не делалось лишней
       перестановки*/
    if (0 == n) return;
 
    T tmp;
    int childPos;
    tmp = x[k];
 
    while (k <= n/2) {
        childPos = 2*k;  // Левый ребенок элемента k
 
        /* выбираем большего ребенка элемента k
           из 2-х: либо левый, либо правый
           */        
        if (childPos < n && x[childPos] < x[childPos + 1]) {
            childPos++;
        }
        /* Если родитель x[k] больше всех своих детей,
           то ничего не делаем, он стоит на правильном месте */
        if(tmp >= x[childPos]) break;
 
        // иначе - меняем x[k] с наибольшим ребенком
        x[k] = x[childPos];
        k = childPos;
    }
    x[k] = tmp;
}
 
template<class T>
void PyramidSort1(T* x, int n) {
    int i;
    T tmp;
 
    // Построение пирамиды 
    for (i = n/2; i >= 0; i--) {
      Screening(x, i, n-1);
    }
 
    /* Формирование конечной отсортированной
       последовательности + "балансирование"
       пирамиды */
    for (i = n-1; i > 0; i--) {
        // меняем первый с последним 
        swap(x, 0, i);
 
        /* Восстановление баланса 
           для пирамиды x[0..i-2] */
        Screening(x, 0, i-1);
    }
}