#include<ctime> // clock
#include<iostream>  // cout
#include<fstream> // ofstream
#include<algorithm> // swap
#include<vector>  // vector

using namespace std;

typedef unsigned uint;


////////////////////////////////////////////////////////////////////////////////

/// D-äres Heapsort ///

enum { D_MIN = 2, D_MAX = 16 };

//
// Sei 'A[0..N-1]' die Arraydarstellung eines D-ären Heaps (linksvollständiger
// D-ärer Baum mit Min-Heapordnung, dessen Knoten sind in 'A' in Levelorder-
// Reihenfolge gespeichert) mit N Knoten und mit einer Fehlstelle am Knoten mit
// Index 'p'. (d.h. verringert man den Schlüssel von 'A[p]' wird 'A' zum Heap).
// Der Aufruf 'BubbleDown(A, N, p, D)' soll 'A' reparieren.
//
// Hinweis:
// 1. Der Schlüssel des Elements 'A[i]' ist 'A[i].Key()'.
// 2a. Schlüssel haben den Typ 'K',
// 2b. zwei Schlüssel 'k0' und 'k1' können mit 'k0<k1', 'k0<=k1', 'k0>k1' und
// 'k0>=k1' verglichen werden.
// 3. Arrayeinträge haben den Typ 'T'.
//
// Für eine effiziente Implementierung:
// 4. Vermeiden Sie den Schlüssel des selben Array-Elements mehrfach zu be-
// rechnen (speichern Sie den Schlüssel in einer lokalen Variable.)
// 5. Vermeiden Sie Einträge, von Vater- und Kindknoten stets zu tauschen, be-
// nutzen Sie folgende Idee:
//   Sei A[i0]=a0, A[i1]=a1, ..., A[iM]=aM eine Sequenz der von 'BubbleDown' be-
//   arbeiteten (d.h. getauschten) Knoten vor der Bearbeitung.
//   Der Effekt von
//     swap(A[i0], A[i1]); swap(A[i1], A[i2]); ... swap(A[i(M-1)], A[iM]);
//   ist
//     A[i0]=a1, A[i1]=a2, ..., A[i(M-1)]=aM, A[iM]=a0.
//   Selbige Belegung kann durch eine Sequenz von Zuweisungen erzeugt werden:
//     T tmp=A[i0]; A[i0]=A[i1]; A[i2]=A[i3]; ... A[i(M-1)]=A[iM]; A[iM]=tmp;
//   Statt drei Zuweisungen (swap) benötigt man nur eine Zuweisung pro Array-
//   zelle zzgl. der Zuweisung von 'tmp'!
//
template<typename T>
inline void BubbleDown(T A[], const uint N, uint p, const uint D)
{
	typedef typename T::key_type K;
	/// TODO Anfang

    uint minChild = p*D + 1;
    T temp = A[p];
    K tempKey = temp.Key();
    bool someChange = false;

	while(p*D + 1 < N) {
        minChild = p*D + 1;
            for (uint i = p*D + 2; i <= p*D + D; i++) {//p * D + 1 + D - 1
                //Wenn N überschritten wird beenden
                if (i == N)
                        break;
                //Wenn aktuelles Minimum größer =>neues Minimum
                if (A[minChild].Key() > A[i].Key()) {
                        minChild = i;
                }
            }

            if (tempKey >= A[minChild].Key()) {
                someChange = true;
                //temp = A[p];
                A[p] = A[minChild];
                //A[minChild] = temp;

                p = minChild;
            }
            else break;
    }
    if(someChange)
      A[p] = temp;




//  bool tempFlag = false;
//  uint minChild = p*D + 1;
//  T temp = A[minChild];
//  uint minChildLast = p;
//
//  while(minChild < N) {
//        for (uint i = p*D + 2; i <= p*D + 1 + D - 1; i++) {
//            //Wenn N überschritten wird beenden
//            if (i >= N)
//                break;
//            //Wenn aktuelles Minimum größer =>neues Minimum
//            if (A[minChild].Key() > A[i].Key()) {
//                minChild = i;
//            }
//        }
//
//        if (A[p].Key() > A[minChild].Key()) {
//          if(!tempFlag) {
//            temp = A[p];
//            tempFlag = true;
//          }
//          A[p] = A[minChild];
//            //BubbleDown(A, N, minChild, D);
//          p = minChild;
//          minChild = p*D + 1;
//          minChildLast = minChild;
//        }
//        else break;
//    }
//
//  A[minChildLast] = temp;
	/// TODO Ende
}

//
// Die Funktion 'MakeHeap(A, N, D)' arrangiert das Array 'A[0..N-1]' in einen
// D-ären Min-Heap um (Heapaufbauphase).
//
// Hinweis:
// 1. In der Heapaufbauphase ist der erste Knoten, an dem etwas zu tun ist, der
// Vater vom Knoten mit Index N-1.
// 2. Die Implementierung ist (fast) ein Einzeiler!
//
template<typename T>
void MakeHeap(T A[], const uint N, const uint D)
{
	/// TODO Anfang

	for (int i = (N - 1) / D; i >= 0; i--) {
		BubbleDown(A, N, i, D);
	}
	/// TODO Ende
}

//
// Vorausgesetzt, das Array 'A[0..N-1]' ist ein D-ärer Min-Heap, sortiert die
// Funktion 'HeapSelect(A, N, D)' das Array 'A' absteigend.
//
// Hinweis:
// 1. Die Funktion 'swap(A[i], A[j])' tasucht die Elemente 'A[i]' und 'A[j]'.
// 2. Die Implementierung ist (fast) ein Einzeiler!
//
template<typename T>
void HeapSelect(T A[], const uint N, const uint D)
{
	/// TODO Anfang
	for (int i = N - 1; i > 0; i--) {
		swap(A[i], A[0]);
		BubbleDown(A, i, 0, D);
	}
	/// TODO Ende
}

//
// Die Funktion 'DAryHeapSort(A, N, D)' sortiert das Array 'A[0..N-1]' mit
// D-ärem Heapsort.
//
template<typename T>
void DAryHeapSort(T A[], const uint N, const uint D)
{
	MakeHeap(A, N, D); HeapSelect(A, N, D);
}


////////////////////////////////////////////////////////////////////////////////

unsigned long long cmps;
unsigned z;

template<uint M>
struct key {
	int x;
	key() {}
	key(int y) : x(y) {}
	bool operator<=(const key& k) const { ++cmps; for (uint i = 0; i<M; z += z + i++); return x <= k.x; }
	bool operator>=(const key& k) const { ++cmps; for (uint i = 0; i<M; z += z + i++); return x >= k.x; }
	bool operator<(const key& k) const { ++cmps; for (uint i = 0; i<M; z += z + i++); return x<k.x; }
	bool operator>(const key& k) const { ++cmps; for (uint i = 0; i<M; z += z + i++); return x>k.x; }
};

template<uint N = 1, uint M = 0>
struct item {
	int x[N];
	item() {}
	item(const int y) { x[0] = y; }
	typedef key<M> key_type;
	key_type Key() const { return key<M>(x[0]); }
};

void Test()
{
	static const char x[] = { '|', '/', '-', '\\', '|', '/', '-', '\\' };
	clock_t t = 0;
	vector< item<1, 0> > A; A.reserve(1u << 20);
	vector<uint> c; c.reserve(A.capacity() / 10 + 1);

	clock_t T = 60 * CLOCKS_PER_SEC + clock(); // 1 Minute
	for (uint i = 0;;) {
		A.resize(1 + (rand() % A.capacity()));
		c.resize(1 + A.size() / 10, 0);
		// Array generieren, Häufigkeiten zählen
		for (uint j = 0; j<A.size(); ++j) {
			const int x = rand() % ((A.size() + 9) / 10);
			A[j] = x; ++c[x];
		}
		// Sortieren
		DAryHeapSort(&A[0], A.size(), D_MIN + (rand() % (D_MAX - D_MIN + 1)));
		// Aufsteigend sortiert?
		--c[A[0].x[0]];
		for (uint j = 1; j<A.size(); ++j) {
			if (!(A[j].Key() <= A[j - 1].Key())) {
				cerr << "\rFehler: Die Ordnung der sortierten Ausgabe stimmt nicht.\n";
				exit(1);
			}
			--c[A[j].x[0]];
		}
		// Keine Elemente mehr/weniger?
		for (uint j = 0; j<c.size(); ++j) {
			if (c[j++] != 0) {
				cerr << "\rFehler: Die sortierte Ausgabe enthält duplizierte Schlüssel.\n";
				exit(1);
			}
		}
		// Mitteilung: Wir stecken in keiner Endlosschleife!
		if (clock() - t >= CLOCKS_PER_SEC / 8) {
			t = clock();
			if (t<T) {
				cout << "\rAbbrechen mit STRG+C. Teste... " << x[i & 7];
			}
			else {
				cout << "\rTest abgeschlossen.             " << endl;
				return;
			}
			++i;
		}
	}
}

template<uint E>
void ScanD()
{
	enum { N = 1000000, R = 50, T = 10 };
	char file[] = { 'd', 'h', 's', 'c', '0' + E, '.', 't', 'x', 't', 0 };
	ofstream oc(file);
	file[3] = 't'; ofstream ot(file);
	// E=0: Objekte klein, Vergleich billig
	// E=1: Objekte groß, Vergleich billig
	// E=2: Objekte klein, Vergleich teuer
	vector< item< E == 1 ? 16 : 1, E == 2 ? 32 : 0> > A; A.resize(N);
	for (uint i = 0; i<A.size(); ++i) A[i] = i;

	for (uint D = D_MIN; D <= D_MAX; ++D) {
		cmps = 0;
		clock_t t0 = clock(), dt;
		uint i = 0;
		while ((dt = clock() - t0)<T*CLOCKS_PER_SEC || i<R) {
			random_shuffle(A.begin(), A.end());
			DAryHeapSort(&A[0], A.size(), D);
			++i;
		}
		cout << '.';
		oc << D << ' ' << double(cmps) / i << endl;
		ot << D << ' ' << double(dt) / i*(1.0 / CLOCKS_PER_SEC) << endl;
	}
}

/// TODO Anfang Exp4
enum { D = 3 }; // hier in Experiment 1 ermittelten Wert für D eintragen
/// TODO Ende Exp4


time_t seed = 0;
int Rand(uint n) { return rand() % n; }


template<uint P>
void RunPhase()
{
	enum { N = 100000, S = 5000, R = 50, T = 10 };

	srand(seed == 0 ? seed = time(NULL) : seed); // RNG zurücksetzen
	char file[] = { 'd', 'h', 's', 'p', '0' + P, '.', 't', 'x', 't', 0 };
	ofstream out(file);
	vector< item<1, 0> > A; A.reserve(N);

	for (uint n = S; n<A.capacity(); n += S) {
		A.resize(n);
		clock_t t0 = clock(), dt;
		uint i = 0;
		cmps = 0;
		while ((dt = clock() - t0)<T*CLOCKS_PER_SEC || i<R) {
			for (uint j = 0; j<A.size(); ++j) A[j] = j;
			random_shuffle(A.begin(), A.end(), Rand);
			switch (P) {
			case 0: MakeHeap(&A[0], A.size(), D); break;
			case 1: DAryHeapSort(&A[0], A.size(), D); break;
			default: break;
			}
			++i;
		}
		out << n << ' ' << double(dt) / i*(1.0 / CLOCKS_PER_SEC) << endl;
		cout << '.';
	}
}

void TimeMakeHeap()
{
	RunPhase<0>(); RunPhase<1>(); RunPhase<2>();
}

////////////////////////////////////////////////////////////////////////////////

template<typename T, int N> int L(T(&A)[N]) { return N; }

static void(*Fn[])() = { Test, ScanD<0>, ScanD<1>, ScanD<2>, TimeMakeHeap };

int main(int argc, char* argv[])
{
	if (argc != 2 || (argc == 2 && !('0' <= *argv[1] && *argv[1]<'0' + L(Fn)))) {
		cerr <<
			"Syntax: dhsort N\n"
			"Der obige Aufruf fuehrt Experiment N aus, dabei ist N eine natuerliche Zahl. Je\n"
			"nach Experiment werden unter Umstaenden Textdateien als Ausgabe erzeugt. Ver-\n"
			"fuegbare Experimente sind:\n"
			" 0 - D-aeres Heapsort wird auf verschiedenen, zufaellig generierten, Arrays ge-\n"
			"     testet.\n"
			" 1 - D-aeres Heapsort wird fuer kleine Objekte mit schnellen Schluesselvergleichen\n"
			"     auf uniform zufaellig gewaehlten Permutationen von {1, 2, ..., n}, fuer ver-\n"
			"     schiedene n ausgefuehrt; Messung von: Vergleichsanzahl, Zeit.\n"
			" 2 - D-aeres Heapsort wird fuer grosse Objekte auf uniform zufaellig gewaehlten\n"
			"     Permtationen von {1, 2, ..., n}, fuer verschiedene n, ausgefuehrt; Messung von\n"
			"     Vergleichsanzahl, Zeit.\n"
			" 3 - D-aeres Heapsort wird fuer langsame Schluesselvergleiche auf uniform zufaellig\n"
			"     gewaehlten Permtationen von {1, 2, ..., n}, fuer verschiedene n, ausgefuehrt;\n"
			"     Messung von: Vergleichsanzahl, Zeit.\n"
			" 4 - D-aeres Heapsort wird fuer kleine Objekte mit schnellen Schluesselvergleichen\n"
			"     auf uniform zufaellig gewaehlten Permutationen von {1, 2, ..., n}, fuer ein festes\n"
			"     n, ausgeuehrt; Messung von: Vergleichsanzahl, Zeit für MakeHeap und HeapSelect.\n";
		return 1;
	}

	const int i = *argv[1] - '0';
	cout << "Experiment " << i << " laeuft";
	Fn[i]();
	cout << endl;
	cin.get();
	return 0;
}