#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <iomanip>
#include <locale>
#include <stdlib.h>
#include <time.h>

#ifdef WINDOWS
#include <Windows.h>
#endif

#ifdef _DEBUG
#define DBG(x) (x)
#else
#define DBG(x) ((void *)0)
#endif

// Since the math for a heap assumes 1-based indexing, 
// this allows us to use 1-based indexing on an existing
// vector.
template <class T>
class one_based {
    std::vector<T> &data;
public:
    one_based(std::vector<T> &data) : data(data) {}
    T &operator[](size_t index) {
        return data[index-1];
    }
    T operator[](size_t index) const {
        return data[index-1];
    }
    size_t size() { return data.size(); }
};

template <class T, class Cmp>
void heapify(std::vector<T> &d, Cmp cmp) {
    one_based<T> data(d);
    for (size_t i=2; i<=data.size(); i++) 
        for (size_t j=i; j>1; j/=2)
            if (cmp(data[j/2], data[j]))
                std::swap(data[j], data[j/2]);
            else break;
}

template <class T>
void heapify(std::vector<T> &d) {
    heapify(d, std::less<T>());
}

template <class T, class Cmp>
bool check_heap(std::vector<T> &d, int N, Cmp cmp) {
    one_based<T> data(d);
    for (int i=1; i<N/2; i++)
        if (cmp(data[i], data[i*2]) || cmp(data[i], data[i*2+1])) {
            std::cerr << "\nHeap corrupted\n";
            return false;
        }	
    return true;
}

template <class T>
bool check_heap(std::vector<T> &d) {
    return check_heap(d, std::less<T>());
}

template <class T, class Cmp>
void sift(std::vector<T> &d, size_t max, Cmp cmp = std::less<T>()) { 
    one_based<T> data(d);
    size_t pos2=2;

    for (size_t pos1=1; pos2<max; pos1=pos2, pos2*=2) {
        if (cmp(data[pos2], data[pos2+1]))
            ++pos2;

        if (cmp(data[pos1], data[pos2]))
            std::swap(data[pos1], data[pos2]);
        else break;
    }
}

template <class T>
void sift(std::vector<T> &d, size_t max) {
    sift(d, max, std::less<T>());
}

template <class T, class Cmp>
void heap_sort(std::vector<T> &data, Cmp cmp) { 
    heapify(data, cmp);

    DBG((check_heap(data, data.size(), cmp)));

    for (size_t pos=data.size()-1; pos>1; pos--) {
        std::swap(data[0], data[pos]);
        sift(data, pos, cmp);

        DBG((check_heap(data, pos-1, cmp)));
    }

    if (cmp(data[1], data[0]))
        std::swap(data[0], data[1]);
}

template <class T>
void heap_sort(std::vector<T> &d) {
    heap_sort(d, std::less<T>());
}

//#ifdef TEST
template <class T, class Cmp>
bool check_sorted(std::vector<T> const &data, Cmp cmp) {
    bool sorted = true;
    for (size_t i=0; i<data.size()-1; i++)
        if (cmp(data[i+1], data[i])) {
            std::cerr << "Mis-sorted: " << data[i] << " and " << data[i+1] << "\n";
            sorted = false;
        }
    return sorted;
}

template <class T>
bool check_sorted(std::vector<T> const &data) {
    return check_sorted(data, std::less<T>());
}

template <class T>
void fill_rand(std::vector<T> &data, size_t size, time_t seed) {
    srand(unsigned(seed));
    data.clear();

    for (size_t i=0; i<size; i++)
        data.push_back((T)rand());
}

#ifdef WINDOWS
class timer {
    LARGE_INTEGER start;
public:
    timer() { QueryPerformanceCounter(&start); }
    
    double duration() {
        LARGE_INTEGER stop;
        LARGE_INTEGER freq;
        
        QueryPerformanceCounter(&stop); 
        QueryPerformanceFrequency(&freq);

        return double(stop.QuadPart-start.QuadPart)/freq.QuadPart;
    }
};
#else
class timer {
    clock_t start;
public:
     timer() : start(clock()) {}
     double duration() {
         return double(clock() - start)/CLOCKS_PER_SEC;
     }
};
#endif

int main() { 
    time_t seed = time(NULL);

    // std::cout.imbue(std::locale("")); fails on ideone.

    for (int i=2; i<12; i++) {
        size_t size = (1 << i) * 1024;
        
        std::vector<long> data;
        fill_rand(data, size, seed);

        timer t;

        heap_sort(data, std::less<long>());

        double d = t.duration();

        DBG((check_sorted(data)));

        std::cout << "size:" << std::setw(12) << size << " time: " << d << "\n";
    }
    return 0;
}

// #endif