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;
        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.


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.