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);
    }

CodePudding user response：

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.