# Building a correct d-max heap bottom up

I want to implement a d-max heap using a bottom-up approach. This way I will start from the last parent in the tree and build myself up to the root of the heap. We will compare children and parents in order to create a d-max heap.

template <typename Comparable>
void buildHeapBottomUp(Comparable arr[], int n, int d)
{
bool check;
do
{
check = false;
for (int i = n - 1; i >= 0; i--)
{
if (arr[i] > arr[(i - 1) / d])
{
int current = i;
int parent = (i - 1) / d;

while (arr[current] > arr[parent]) //swap to create d-max heap
{
check = true;
swap(arr[current], arr[parent]);
current = parent;
parent = (current - 1) / d;
}
}
}
} while (check == true);
}


The code above is not really sufficient, as I'm starting from the last element in the array and not the last parent. This way I'm not building the d-max heap correctly bottom up, as some elements seem to get out of place. To fix this I have implemented a do-while loop to keep track of the process and which will continue to loop until the d-max heap is correct. But as you can guess this approach is just patching the process.

Therefore, I want to do this correctly and I'm hoping to get some help to build a d-max heap bottom up.