Max Heap插入函数实现C＆＃x2B;＆＃x2B;

Question

我正在尝试将钥匙值插入堆中。我正在使用testunit.cpp出错。我得到了这些错误：

断言失败了。 预期：＆lt; [（10,100），（7,70），（6,60），（5,50），（2,20），（1,10），（1,10），（3,30），（4,40） ]＆gt; 实际：＆lt; [（7,70），（5,50），（6,60），（4,40），（2,20），（1,10），（1,10），（3,30），（10,100） ]＆gt;

断言失败了。 预期：＆lt; [（10,100），（4,40），（5,50），（1,10），（2,20），（3,30），（3,30）]＆gt; 实际：＆lt; [（（5,50），（4,40），（3,30），（1,10），（2,20），（10,100），（10,100）]＆gt;

断言失败了。 预期：＆lt; [（9,90），（7,70），（8,80），（6,60），（2,20），（1,10），（1,10），（3,30），（5，5， 50）]＆gt; 实际：＆lt; [（9,90），（7,70），（8,80），（5,50），（2,20），（1,10），（1,10），（3,30），（6，6，， 60）]]＆gt;

断言失败了。 预期：＆lt; [（6,60），（5,50），（4,40），（1,10），（2,20），（3,30），（3,30）]＆gt; 实际：＆lt; [（6,60），（5,50），（3,30），（1,10），（2,20），（4,40）]＆gt;

我的插入功能是：

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

            }
        }
    } 

我的堆功能是：

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应该从子女跳到父母。
• 此外，当实现上一点点时，当不再发生交换时，该循环可能会退出。