#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
/*
bool less(int i, int j) {
	return i<j;
//	return pq[i].compareTo(pq[j]) < 0;
}
*/
void exch(vector<int>& v, int i, int N) {
	int t = v.at(i-1);
	v.at(i-1) = v.at(N-1);
	v.at(N-1) = t;
}

void sink(vector<int>& v, int i, int N) {
	while (2*i <= N) {
		int j = 2*i;
		if ((j < N) && (v.at(j)<v.at(j+1))) {
			j++;
		}
		if (!(v.at(i) < v.at(j))) {
			break;
		}
		exch(v, i, j);
		i = j;
	}
}

void heapsort(vector<int>& v) {
	int N = v.size();
	for (int k=N/2; k>=1; k--) {
//		cout << "Er að fara að sinka gildinu " << v.at(k) << endl;
		sink(v, v.at(k), N);
	}
	while (N>1) {
		N = N-1;
		exch(v, 1, N);
		sink(v, 1, N+1);
	}
}

bool issorted(vector<int>& v) {
    /*
     * Athugar hvort vigurinn v sé í stígandi röð
     */
    cout << endl;
    for (int i = 1; i < v.size(); i++) {
        if (v[i] < v[i - 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    // Prófum sort á vigrum af lengdunum 0, 101, og 1000:
    vector<int> sizes = {0, 101};
    for (int n : sizes) {
        // Upphafstillum v með tölunum 0 upp í n-1 í slembinni röð
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = i;
        }
        random_shuffle(v.begin(), v.end());

		// JÖS PRÓFUN
        for (int i = 0; i < n; i++) {
			cout << i << ": " << v[i] << endl;
		}

        // Röðum v aftur
        heapsort(v);

		//JÖS PRÓFUN
		cout << "Kallað á heapsort" << endl;
        for (int i = 0; i < n; i++) {
			cout << i << ": " << v[i] << endl;
		}

        // Athugum hvort röðunin tókst
        if (issorted(v)) {
            cout << "Röðun á " << v.size() << " staka vigri tókst" << endl;
        } else {
            cout << "Röðun á " << v.size() << " staka vigri mistókst" << endl;
        }
    }
}