c++ - 最小二进制堆问题

Question

我需要有关此 minheap 代码的帮助:

#include < vector>

using namespace std;

class heap {

    vector <int> v;

    public:

        int hSize()
        {
            return v.size();
        }

        int rsize()
        {
            return  hSize() - 1;
        }    

        int parent(int i) 
        {
            return (i - 1) / 2;
        }

        int left(int i)
        {
            return i * 2 + 1;
        }

        int right(int i)
        {
            return i * 2 + 2;
        }

        void swap(int i, int j)
        {
            int temp = v[j];
            v[j] = v[i];
            v[i] = temp;
        }

        void push(int e)
        {

            v.push_back(e);
            int id = rsize(); 

            if (hSize() > 1)
                while (v[parent(id)] > v[id]) {               
                    swap(parent(id), id);
                    id = parent(id);
                }
        }

        int pop ()
        {

          int f = 0;  
          int p = v[0];

          v[0] = v[rsize()];

          if (hSize() > 1) {
              while (v[left(f)] < v[f] || v[right(f)] < v[f]) {
                    if (v[left(f)] < v[f] && v[right(f)] < v[f]) {
                        if (v[left(f)] < v[right(f)]) {
                            swap(left(f), f);
                            f = left(f);
                    }
                    else { 
                            swap(right(f), f);
                            f = right(f);
                    }
                }

                else {
                    if (v[left(f)] < v[f]){
                         swap(left(f), f);
                         f = left(f);
                    }
                    else {
                         swap(right(f), f);
                         f = right(f);
                        }
                    }
                } 
          }
          else { }

          v.resize(rsize());
          return p;
        }

        void show()
        {
            if (hSize() > 0) {
                cout << "Heap content: ";
                for (int i = 0; i < hSize(); i++) cout << v[i] << " ";
            }
            else cout << "\nHeap successfully emptied!";  
            cout << "\n";          
        }

        bool Empty()
        {
            return v.empty();
        }

        ~heap()
        {
            v.clear();
        }

    };         

好吧，除了当它弹出屏幕上的最后一个元素时它打印一个随机数之外，代码几乎做对了所有事情。你怎么看？

谢谢!

Answer 1

您有两个类似的问题，一个在 push() 中，一个在 pop() 中。在推送中，您需要在查看 v[parent(id)] 之前检查 id != 0。如果 id == 0 你在根目录，你应该停止。同样，在 pop() 中，您应该在访问 之前检查 right(f)(或 left(f))是否在 vector 内>v[right(f)](或 v[left(f)])。如果不是，则您已到达堆的底部，您应该停止。