#include<iostream>
#include<ctime>
#include<cstdlib>
#include<stdio.h>
#include <cmath>
using namespace std;
class BinaryHeap{
    public:
    double* my_array;
    int capacity;
    int heapsize;

    BinaryHeap(double* tmparray,int size)
    {
        my_array = tmparray;
        capacity = size;
        heapsize = size;;
    }
    void heapify(int current)
    {
        int largest = current;
        double temp;
        int left = (2 * current) + 1;
        int right = (2 * current) + 2;
        if (left < heapsize && my_array[left] > my_array[largest])
            largest = left;

        if (right < heapsize && my_array[right] > my_array[largest])
            largest = right;

        if (largest != current) {
            temp = my_array[largest];
            my_array[largest] = my_array[current];
            my_array[current] = temp;
            heapify(largest);
        }
    }
    void buildHeap() {
        for (int i = heapsize - 1; i >= 0; i--)
            heapify(i);
    }

    void heapSort() {
        int temp = heapsize;
        for (int i = heapsize - 1; i >= 0; i--) {
            double container = my_array[0];
            my_array[0] = my_array[i];
            my_array[i] = container;
            heapsize = heapsize - 1;
            heapify(0);
        }
        heapsize = temp;
    }
    void printSome() {
        for (int i = 1000000; i < 1000100; i++) {
            cout << my_array[i] << ' ';
        }
    }
};
int main() {
    srand(unsigned(time(NULL)));
    const int size = 10000000;
    double* tab = new double[size];
    for (int i = 0; i < size; i++) {
        tab[i] = ((rand() << 15) + rand()) / (double)pow(2,30);
    }
    clock_t begin, end;
    double time_spent;



    BinaryHeap* myheap = new BinaryHeap(tab, size);
    myheap->buildHeap();
    begin = clock();
    myheap->heapSort();
    //myheap->printSome();
    end = clock();
    time_spent = ((double)end - (double)begin) / CLOCKS_PER_SEC;
    cout <<endl<< "Time spent:" << time_spent;
    return 0;
}