1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.