#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;
    	
    	std::cout << "start minchild2" << std::endl;
     
    	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];
    		
    		std::cout << "else minchild2" << std::endl;
    		for(int i = first_child; i <= last_child; i++)
    			if(a[i] > min_key){
    				min_key = a[i];
    				minchild = i;
    				std::cout << "for loop minchild2" << std::endl;
    			}
    		std::cout << "return minchild2" << std::endl;
    		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;
    }