terminating with uncaught exception of type std::out_of_range: vector for removeMin() function in heap

  c++, heap, priority-queue, uncaught-exception

I am getting this error "libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: vector" for my heapifyDown() I believe. This is the cpp for my priorityqueue. I call heapifyDown() in my removeMin() so I made some changes there but my heapifyDown() seems fine to me. Can anyone help me troubleshoot this?

#include <iostream>
#include "json.hpp"

#include "priorityqueue.h"
using namespace std;

PriorityQueue::PriorityQueue(std::size_t max_size) :
    nodes_(max_size + 1, KeyValuePair()),
    max_size_(max_size),  // largest heap can be
    size_(0) {  // actual size of heap
}

void PriorityQueue::insert(Key k) {
    insert(std::make_pair(k, std::make_pair(0, 0)));
    size_++;
}

void PriorityQueue::insert(KeyValuePair kv) {
    // Inserts a key-value pair into the priority queue.
    // The types Key, Value, and KeyValuePair are defined
    // in priorityqueue.h using typedefs.
    nodes_.push_back(std::make_pair(kv.first, kv.second));
}

KeyValuePair PriorityQueue::min() {
    // Returns the KeyValuePair that has
    // the minimum Key in the heap.
    int minIndex;
    int minKey;
    for (int i = 0; i < sizeof(nodes_); i++) {
        Key key = getKey(i);
        if (key < minKey) {
            minIndex = i;
            minKey = key;
        }
    }

    return nodes_.at(minIndex);
}

KeyValuePair PriorityQueue::removeMin() {
    // Returns and removes the KeyValuePair
    // that has the minimum Key in the heap.
    KeyValuePair min = PriorityQueue::min();
    KeyValuePair root = nodes_.at(size_ - 1);
    //inodes_.at(0) = nodes_.at(nodes_.size() - 1);
    //KeyValuePair min = nodes_.pop_back();
    //heapifyDown(0);

    if (isEmpty())
        cout << "Heap is empty" << endl;
    else {
        nodes_.at(0) = root;
        size_--;
        if (size_ > 0)
            heapifyDown(0);
    }
    return min;
}

bool PriorityQueue::isEmpty() const {
    // Returns true if and only if the heap is empty.
    return size_ == 0;
}

size_t PriorityQueue::size() const {
    // Returns the number of KeyValuePairs in the heap
    return sizeof(nodes_);
}

nlohmann::json PriorityQueue::JSON() const {
    nlohmann::json result;
  for (size_t i = 1; i <= size_; i++) {
      nlohmann::json node;
      KeyValuePair kv = nodes_[i];
      node["key"] = kv.first;
      node["value"] = kv.second;
      if (i != ROOT) {
          node["parent"] = std::to_string(i / 2);
      }
      if (2 * i <= size_) {
          node["leftChild"] = std::to_string(2 * i);
      }
      if (2 * i + 1 <= size_) {
          node["rightChild"] = std::to_string(2 * i + 1);
      }
      result[std::to_string(i)] = node;
  }
  result["metadata"]["max_size"] = max_size_;
  result["metadata"]["size"] = size_;
    return result;
}

void PriorityQueue::heapifyUp(size_t i) {
    // swimup, percolates the ith
    // node up the heap to ensure the heap property
    // is preserved.
    if (i >= 0 && nodes_.at(Parent(i)) > nodes_.at(i))
    {
        // swap the nodes if true
        swap(nodes_.at(i), nodes_.at(Parent(i)));

        // call heapifyUp
        heapifyUp(Parent(i));
    }
}

void PriorityQueue::heapifyDown(size_t i) {
    // sink, percolates the ith
    // node down the heap to ensure the heap
    // property is preserved.
    // left and right node
    int left = LEFT(i);
    int right = RIGHT(i);

    int smallest = i;

    // compare ith node to left and right node to find min
    if (left < size() && nodes_.at(left) < nodes_.at(i))
        smallest = left;
    else
        smallest = i;

    if (right < size() && nodes_.at(right) < nodes_.at(smallest))
        smallest = right;

    // if smallest is left or right, continue
    if (smallest != i) {
        swap(nodes_.at(i), nodes_.at(smallest));
        heapifyDown(smallest);
    }
}

void PriorityQueue::removeNode(size_t i) {
    // Removes the ith node from the heap.
    // replace node i with the rightmost node and then heapifyDown
    nodes_.at(i) = nodes_.back();
    nodes_.pop_back();
    heapifyDown(i);
    size_--;
}

Key PriorityQueue::getKey(size_t i) {
    //  Returns the key of the ith node in the heap.
    KeyValuePair pair = nodes_.at(i);
    Key key = pair.first;
    return key;
}

size_t PriorityQueue::RIGHT(size_t i) {
    return (2 * i + 2);
}

size_t PriorityQueue::LEFT(size_t i) {
    return (2 * i + 1);
}

size_t PriorityQueue::Parent(size_t i) {
    return (i - 1) / 2;
}

Source: Windows Questions C++

LEAVE A COMMENT