package App.Model;

import java.util.List;
import java.util.Vector;

public class HeapSorter
{
    private long time = 0;
    public long getTime() { return time; }

    private long exchanges = 0;
    public long getExchanges() { return exchanges; }

    private long comparison = 0;
    public long getComparison() { return comparison; }

    public HeapSorter() { }

    /**
     * Демонстрационный алгоритм для пирамидальной сортировки
     * Авторы алгорифма - J. W. J. Williams и R. W. Floyd
     *
     * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
     *
     * @author Jason Harrison@cs.ubc.ca
     * @version 1.0, 23 Jun 1995
     */

    public void sort(int a[]) throws Exception {

        time = 0;
        exchanges = 0;
        comparison = 0;

        long startTime = System.currentTimeMillis();

        int N = a.length;
        //Создаём из массива сортирующее дерево
        //Максимальный элемент окажется в корне.
        for (int k = N / 2; k > 0; k--) downheap(a, k, N);
        //Избавляемся от максимумов
        //и перетряхиваем сортирующее дерево
        do {
            //Меняем максимум с последним элементом...
            int T = a[0];
            a[0] = a[N - 1]; exchanges++; //TODO ОБМЕН
            a[N - 1] = T;
            //... и перестравиваем сортирующее дерево
            //для неотсортированной части массива
            N = N - 1;
            downheap(a, 1, N);
        } while (N > 1); //До последнего элемента

        long stopTime = System.currentTimeMillis();
        time = stopTime - startTime;
    }

    //Просматриваем ветку и в её корень перемещаем крупнейший узел
    private void downheap(int a[], int k, int N) throws Exception {
        //В корне поддерева
        //запоминаем родителя
        int T = a[k - 1];
        //Смотрим потомков в пределах ветки
        while (k <= N / 2) {
            int j = k + k;//Левый потомок
            //Если есть правый потомок,
            //то сопоставляем его с левым
            //и из них выбираем крупнейший
            comparison++; //TODO СРАВНЕНИЕ
            if ((j < N) && (a[j - 1] < a[j])) j++;
            //Если родитель огромнее (либо равен) наибольшего потомка
            //то значит всё в порядке в этой ветке
            comparison++; //TODO СРАВНЕНИЕ
            if (T >= a[j - 1]) break;
            else { //Если родитель поменьше наибольшего потомка...
                //... то потомок становится на место родителя
                a[k - 1] = a[j - 1]; exchanges++; //TODO ОБМЕН
                k = j;
            }
        }
        //Родитель в результате меняется местами с наибольшим из потомков
        //(либо остаётся на своём месте, если все потомки поменьше его)
        a[k - 1] = T; exchanges++; //TODO ОБМЕН
    }
}