#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

void heapSort(int heap[], const int antal);
void nodeSort(int heap[], const int antal, int start);

int main()
{
    const int antal = 30000;
    int heap[antal];
    srand(time(NULL));
    heapSort(heap, antal);
    return 0;
}

void heapSort(int heap[], const int antal) {
    for (int i = 0; i < antal; i++) {
        heap[i] = (rand() % 150000) + 1;
        cout << heap[i] << "\t";
        if (i % 5 == 0 && i != 0) {
            cout << endl;
        }
    };

    int start = antal / 2; // För att få ut sista noden som har ett eller fler barn
    while (start >= 0) {
        nodeSort(heap, start, antal - 1);
        start--;
    }
    int end = antal - 1;
    while (end > 0) {
        int temp = heap[0];
        heap[0] = heap[end];
        heap[end] = temp;
        nodeSort(heap, 0, end - 1);
        end--;
    }
    cout << endl << endl;
    for (int i = 0; i < antal; i++) {
        cout << heap[i] << "\t";
        if (i % 5 == 0 && i != 0) {
            cout << endl;
        }
    };
}

void nodeSort(int heap[], int start, int end) {
    int root = start;
    int child, temp;

    while (root * 2 < end) {
        child = root * 2;
        if (child < end && heap[child] < heap[child + 1]) {
            child = child + 1;
        }
        if (heap[root] < heap[child]) {
            temp = heap[root];
            heap[root] = heap[child];
            heap[child] = temp;
            root = child;
        }
        else {
            break;
        }
    }
}