C++ Max Heap not sorting correctly after remove max

Question

I'm attempting to remove the max by swapping the first and last element of the vector and then using pop_back. When I remove max I output max but the reordering process is not working correctly and I cannot figure out why.

I have attempted changing the way I am testing multiple times and the results do not change. Can anyone see where I have gone wrong?

#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

Your math is completely wrong. You're confusing stored values with index calculations. In some places you are calculating values by multiplying indexes, in other you are calculating indexes by multiplying stored values. That's never going to work.

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