Max Heap Insert Function Implementation C++

June 3, 2022

I’m trying to insert key values into heap. I’m using TestUnit.cpp for errors. I got these errors:

Assert failed.
Expected:<[(10,100),(7,70),(6,60),(5,50),(2,20),(1,10),(3,30),(4,40)]>
Actual:<[(7,70),(5,50),(6,60),(4,40),(2,20),(1,10),(3,30),(10,100)]>

Assert failed.
Expected:<[(10,100),(4,40),(5,50),(1,10),(2,20),(3,30)]>
Actual:<[(5,50),(4,40),(3,30),(1,10),(2,20),(10,100)]>

Assert failed.
Expected:<[(9,90),(7,70),(8,80),(6,60),(2,20),(1,10),(3,30),(5,50)]>
Actual:<[(9,90),(7,70),(8,80),(5,50),(2,20),(1,10),(3,30),(6,60)]>

Assert failed.
Expected:<[(6,60),(5,50),(4,40),(1,10),(2,20),(3,30)]>
Actual:<[(6,60),(5,50),(3,30),(1,10),(2,20),(4,40)]>

My insert function is :

void insert(KeyValueType const& keyValue)
    {

        size_t asize = size();
        if (asize == 0)
        {
            table.push_back(keyValue);
        }
        else
        {
            table.push_back(keyValue);
            for (int i = asize / 2 - 1; i >= 0; i--)
            {
                heapify(i);

            }
        }
    }

and my heapify function is :

void heapify(size_t index)
    {
        auto previous_index = index;
        do
        {
            previous_index = index;
            auto largest = getLargestFromParentAndHisChildren(index);
            if (index != largest)
            {
                std::swap(table[index], table[largest]);
                index = largest;
            }
        } while (index != previous_index);
    }

>Solution :

Your loop starts at the wrong value. It should be:

for (int i = (asize - 1) / 2; i >= 0; i--)

Not your question, but:

calling heapify is not the fastest way to bubble a value up, since that function needs to check also the sibling value, which is unnecessary.
i-- will make this loop O(n), which is not the complexity you would want for a heap. This operation should be O(logn), and so i should jump from child to parent, in each iteration.
Moreover, when the previous point is implemented, this loop could exit when no more swap occurs.