最大堆插入函数实现C++

Question

我正在尝试将键值插入堆中。我正在使用 TestUnit.cpp 来处理错误。我收到这些错误：

断言失败。预期：<[(10,100),(7,70),(6,60),(5,50),(2,20),(1,10),(3,30),(4,40)] > 实际：<[(7,70),(5,50),(6,60),(4,40),(2,20),(1,10),(3,30),(10,100)] >

断言失败。预期：<[(10,100),(4,40),(5,50),(1,10),(2,20),(3,30)]> 实际：<[(5,50),(4,40),(3,30),(1,10),(2,20),(10,100)]>

断言失败。预期：<[(9,90),(7,70),(8,80),(6,60),(2,20),(1,10),(3,30),(5,50 )]> 实际：<[(9,90),(7,70),(8,80),(5,50),(2,20),(1,10),(3,30),(6,60 )]>

断言失败。预期：<[(6,60),(5,50),(4,40),(1,10),(2,20),(3,30)]> 实际：<[(6,60),(5,50),(3,30),(1,10),(2,20),(4,40)]>

我的插入函数是：

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

            }
        }
    }

我的 heapify 函数是：

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

Answer 1

您的循环从错误的值开始。应该是：

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

不是你的问题，而是：

调用 heapify 并不是使值冒泡的最快方法，因为该函数还需要检查兄弟值，这是不必要的。
i-- 将使这个循环成为 O(n)，这不是您希望堆的复杂性。此操作应该是 O(logn)，因此 i 应该在每次迭代中从子节点跳到父节点。
此外，当前面的点被实现时，当没有更多的交换发生时，这个循环可以退出。

最大堆插入函数实现C++

Max Heap Insert Function Implementation C++

c++

data-structures

heap

max-heap