C++ Max Heap 在移除 max 后排序不正确

Question

我试图通过交换向量的第一个和最后一个元素然后使用 pop_back 来删除最大值。当我删除 max 时，我输出 max 但重新排序过程无法正常工作，我无法弄清楚原因。

我多次尝试改变测试方式，但结果没有改变。谁能看出我哪里出错了？

#include <vector>
#include <string>

class Heap
{
public:
    void insert(int data)
    {
        int parent = 0;

        heap.push_back(data);
        current = heap.size() - 1;
        parent = (current - 1) / 2;

        if (heap.size() > 1)
        {
            while (heap.at(parent) < heap.at(current))
            {
                if (heap.at(current) > heap.at(parent))
                {
                    std::swap(heap.at(parent), heap.at(current));
                    current = parent;
                    parent = (parent - 1) / 2;
                }
            }
        }
        // for(int i = 0; i < heap.size(); i++)
        //      {
        //          std::cout << heap.at(i) << std::endl;
        //      }
        //  std::cout << std::endl;
    }

    void remove_max()
    {
        if (!heap.empty())
        {
            if (heap.size() == 1)
            {
                heap.pop_back();
                return;
            }
            std::swap(heap.at(0), heap.at(heap.size() - 1));
            heap.pop_back();
            int parent = heap.at(0);
            int lchild = (parent * 2) + 1;
            int rchild = (parent * 2) + 2;

            // while(lchild < heap.size() && rchild < heap.size())
            //  {
            //      if(heap.at(lchild) < heap.at(rchild))
            //      {
            //          std::swap(heap.at(parent), heap.at(rchild));
            //          parent = rchild;
            //      }
            //      else
            //      {
            //          std::swap(heap.at(parent), heap.at(lchild));
            //          parent = rchild;
            //      }

            //      lchild = (lchild * 2) + 1;
            //      rchild = (rchild * 2) + 2;
            //  }

            if (lchild < rchild)
            {
                while (parent > lchild)
                {
                    std::swap(heap.at(parent), heap.at(lchild));
                    lchild = (lchild * 2) + 1;
                    parent = (rchild - 1) / 2;
                }
            }
            else
            {
                while (parent > rchild)
                {
                    std::swap(heap.at(parent), heap.at(rchild));
                    rchild = (rchild * 2) + 2;
                    parent = (rchild - 1) / 2;
                }
            }
        }
        // for(int i = 0; i < heap.size(); i++)
        //  {
        //      std::cout << heap.at(i) << std::endl;
        //  }
        // std::cout << std::endl;
        return;
    }

    int max()
    {
        return heap.at(0);
    }

    bool empty()
    {
        return heap.empty();
    }

private:
    std::vector<int> heap;
    int current = 0;
};

int main()
{
    // TODO: implement!
    Heap myHeap;
    std::string command;
    int data;

    do
    {
        std::cin >> command;

        if (command == "add")
        {
            std::cin >> data;
            myHeap.insert(data);
        }
        else if (command == "run")
        {
            std::cout << myHeap.max() << std::endl;
            myHeap.remove_max();
        }
        else if (command == "exit")
        {
            while (!myHeap.empty())
            {
                std::cout << myHeap.max() << std::endl;
                myHeap.remove_max();
            }
        }
    } while (command != "exit");
    return 0;
}

Answer 1

你的数学完全错了。您将存储值与索引计算混淆了。在某些地方，您通过乘以索引来计算值，而在其他地方，您通过乘以存储的值来计算索引。那永远行不通。

void remove_max()
{
    if (heap.empty())
        return;

    std::swap(heap.at(0), heap.at(heap.size() - 1));
    heap.pop_back();

    size_t parent = 0;
    do
    {
        // get first child slot
        size_t child = 2*parent + 1;
        if (child < heap.size())
        {
            // calculate right-child index.
            size_t rchild = 2*(parent+1);
            if (rchild < heap.size() && heap[rchild] > heap[child])
                child = rchild;

            // got the child slot. now compare.
            if (heap[child] > heap[parent])
            {
                std::swap(heap[child], heap[parent]);
                parent = child;
            }
            else
            {
                // parent larger than children. stop here.
                break;
            }
        }
        else
        {
            // reached a node with no children
            break;
        }

    } while (true);
}

C++ Max Heap 在移除 max 后排序不正确

C++ Max Heap not sorting correctly after remove max

c++

vector

max-heap