#include <iostream>
using namespace std;

template <typename T>
void sink(T arr[], int pos, int N, int d) {
    int start(pos*d + 1), max_index(start);
    while(start < N) {
        // Find the max amongst direct "children" of position `pos`
        for(int i = start + 1; (i < start + d) && (i < N); i++) {
            if (arr[i] > arr[max_index]) {
                max_index = i;
            }
        }
        // If arr[pos] is less than the max we found, switch them and proceed
        if (arr[pos] < arr[max_index]) {
            // Switch arr[pos] and arr[max_index] to enforce heap condition
            T tmp = arr[pos];
            arr[pos] = arr[max_index];
            arr[max_index] = tmp;
            // Update pos and start to sink "recursively"
            pos = max_index;
            start = pos*d + 1;
            max_index = start;
        } else { // Else, there is nothing to worry about further ...
            break;
        }
    }
}

template <typename Comparable>
void buildHeap(Comparable arr[], int n, int d) {
    // 1. The first index that might have children is n/d, not (n/d) - 1 !
    //    Be careful of how integer division works ...
    for (int i = (n/d); i>=0; --i){
        sink(arr, i, n, d);
    }
}

template <typename Comparable>
Comparable removeFromHeap(Comparable heap[], int n, int d) {
    Comparable root = heap[0];
    heap[0] = heap[n-1];
    sink(heap, 0, n-1, d);
    return root;
}

template <typename T>
void dheapsort(T arr[], int N, int d) {
    buildHeap(arr, N, d);
    while (N > 1) {
        T tmp = removeFromHeap(arr, N, d);
        arr[--N] = tmp;
    }
}

int main() {
    int test[10] = {1, 3, 2, 5, 6, 8, 2, 8, 10, 11};
    dheapsort(test, 10, 3);
    for (int i = 0; i < 10; i++)
        cout << "test[" << i << "] : " << test[i] << endl;
    return 0;
}