#include <algorithm>
#include "dheap.h"

const int d = 19;

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

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

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