#include <iostream>
using namespace std;

#include <algorithm>
#include <iostream>

#define SIZE 60000

const int d = 19;

//Всплытие
void siftup(int *a, int i){
	int p = (i - 1) / d;
	while((i != 0) && (a[p] > a[i])){
		std::swap(a[i], a[p]);
		i = p;
		p = (i - 1) / d;
	}
}

//n - длина массива
int min_child(int *a, int i, int n){
	if(i*d + 1 >= n) return 0;
	else{
		int s = i*d + 1;
		int min_key = a[s];
		int last = (i + 1)*d;
		if(last >= n) last = n - 1;
		for(int j = s+1; j <= last; j++){
			if(min_key > a[j]){
				min_key = a[j];
				s = j;
			}
			return s;
		}
	}
}

int min_child2(int *a, int i, int n){
	int minchild = 0;

	if(i*d + 1 > n) return 0;
	else{
		int first_child = i*d + 1;
		int last_child = std::min((1 + i)*d - 1, n);
		int min_key = a[first_child];
		for(int i = first_child; i <= last_child; i++)
			if(a[i] > min_key){
				min_key = a[i];
				minchild = i;
			}
		return minchild;
	}
}

//Погружение
void siftdown(int *a, int i, int n){
	int s = min_child2(a, i, n);
	std::cout << "min_child called" << std::endl;
	while((s != 0) && (a[i] > a[s])){
		std::cout << "while loop" << std::endl;
		std::swap(a[i], a[s]);
		i = s;
		s = min_child2(a, s, n);
	}
}

//Преобразование массива в кучу
void build_dheap(int *a, int n){
	for(int i = (n - 1)/*/d*/; i >= 0; i--)
		siftdown(a, i, n);
	std::cout << "after siftdown" << std::endl;
}

int main() {
	int a[SIZE];
	
	for(int i = 0; i < SIZE; i++)
		a[i] = i % 19;
	
	build_dheap(a, SIZE);
	return 0;
}