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++