Проблема с минимальной двоичной кучей

Отладка

• Вы можете запустить код с помощью valgrind, чтобы увидеть, сообщает ли он о каких-либо ошибках.
• Вы можете запустить код в отладчике (отладка занимает больше времени, но больше шансов на успех).

Кодирование. Вы должны использовать утверждения. Например, первая строка функции swap может быть assert(i >= 0 && i < v.size()); и аналогично для j. Я подозреваю, что включение этих двух утверждений покажет вам ошибки. Когда вы закончите, вы можете, если хотите, закомментировать утверждения (хотя некоторым людям нравится оставлять некоторые утверждения всегда).

Обновить Ваш код в порядке. Просто нужно было добавить проверку границ внутри свопа и вернуться, если она не удовлетворена. Вот код и тестовый пример (который прошел, когда я запустил):

#include <vector>
#include <iostream>
#include <cassert>
#include <cstdlib>

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)
        {
            //assert(i >= 0 && i < v.size()); 
            //assert(j >= 0 && j < v.size()); 
            if(i >= v.size() || j >= v.size()) return;
            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();
        }

};


int main()
{
        heap h;
        for(int i = 0; i < 10; i++) {
        h.push(rand()%10);
        h.push(4);
        h.push(3);
        h.push(2);
        h.push(1);
        h.push(0);
        h.push(5);
        h.push(-6);
        h.push(7);
        h.show();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.show();
        }
}

После ввода утверждения я запустил код в отладчике и обнаружил, что сбой произошел в строке swap(right(f), f);, а right(f) вышел за пределы.

У вас есть две похожие проблемы, одна в push() и одна в pop(). В push вам нужно проверить это id != 0, прежде чем смотреть на v[parent(id)]. Если id == 0вы находитесь в корне и вам следует остановиться. Точно так же в pop() вы должны проверить, находится ли right(f) (или left(f)) в пределах вектора, прежде чем обращаться к v[right(f)] (или v[left(f)]). Если это не так, вы достигли дна кучи и должны остановиться.