Return to Question

class BinaryHeap { public: BinaryHeap(int); // constructor that takes the capacity of the structure ~BinaryHeap(); // destructor void insert(int); // inserts a new element to the heap void deleteMin(); // removes the minimum element from the heap int getMin(); // returns the minimum element int the heap, returns -1 if the heap is empty private: int *heap; // array to store the elements of the heap int size; // keeps the number of elements in the heap int capacity; // keeps the total capacity of the heap void percolateDown(int); void percolateUp(int); void swap(int, int); }; BinaryHeap::BinaryHeap(int capacity) { this->capacity = capacity; heap = new int[capacity+1]; size = 0; } BinaryHeap::~BinaryHeap() { delete [] heap; } void BinaryHeap::insert(int element) { if (size < capacity) { size++; heap[size] = element; percolateUp(size); } else return; } void BinaryHeap::deleteMin() { if (size < 1) return; else { heap[1] = heap[size]; size--; percolateDown(1); } } int BinaryHeap::getMin() { if (size < 1) return -1; else return heap[1]; } void BinaryHeap::percolateDown(int hole) { int leftChildIndex, rightChildIndex, minIndex; leftChildIndex = hole * 2; rightChildIndex = hole * 2 + 1; if (rightChildIndex >= size) { if (leftChildIndex >= size) return; else minIndex = leftChildIndex; } else { if (heap[leftChildIndex] <= heap[rightChildIndex]) minIndex = leftChildIndex; else minIndex = rightChildIndex; } if (heap[hole] > heap[minIndex]) { swap(heap[hole], heap[minIndex]); percolateDown(minIndex); } } void BinaryHeap::percolateUp(int index) { int parentIndex(1); if (index != 1) { parentIndex = index / 2; } if (heap[parentIndex] > heap[index]) { swap(heap[parentIndex], heap[index]); percolateUp(parentIndex); } } void BinaryHeap::swap(int i, int j) { int t = heap[i]; heap[i] = heap[j]; heap[j] = t; } 

The following is the main function for testing:

#include <iostream> #include <cassert> #include "BinaryHeap.h" using namespace std; int main () { cout << "Testing your heap implementation..." << endl << endl; BinaryHeap heap(10); // BASICS cout << "Testing insert for a single item..." << endl; heap.insert(3); assert(heap.getMin() == 3); heap.deleteMin(); // INSERT cout << "Testing insert..." << endl; heap.insert(5); heap.insert(10); heap.insert(4); heap.insert(2); heap.insert(56); heap.insert(34); // GETMIN cout << "Testing getMin..." << endl; assert(heap.getMin() == 2); // DELETEMIN cout << "Testing deleteMin..." << endl; heap.deleteMin(); heap.deleteMin(); // GETMIN AFTER DELETEMIN cout << "Testing getMin after deleteMin..." << endl; assert(heap.getMin() == 5); // EXCESSIVE DELETEMIN cout << "Testing deleteMin on an empty heap..." << endl; heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); // GETMIN AFTER EXCESSIVE DELETEMIN cout << "Testing deleteMin on an empty heap..." << endl; assert(heap.getMin() == -1); //IF THERE ARE TWO CHILDREN NODES THAT ARE BOTH SMALLER THAN THE PARENT, SWAP SMALLER cout << "Testing percolate down If there are two children nodes that are both smaller than the parent... " << endl; heap.insert(23); heap.insert(43); heap.insert(234); heap.insert(321); heap.insert(243); cout << "Testing percolate down If there are two children nodes that are both smaller than the parent..." << endl; assert(heap.getMin() == 23); heap.deleteMin(); assert(heap.getMin() == 43); heap.deleteMin(); assert(heap.getMin() == 234); heap.deleteMin(); assert(heap.getMin() == 243); heap.deleteMin(); assert(heap.getMin() == 321); heap.deleteMin(); // DUPLICATE ELEMENTS cout << "Testing insert with duplicate values..." << endl; heap.insert(5); heap.insert(10); heap.insert(4); heap.insert(4); heap.insert(2); heap.insert(56); heap.insert(10); heap.insert(34); // GETMIN WITH DUPLICATE ELEMENTS cout << "Testing getMin..." << endl; assert(heap.getMin() == 2); // EXCESSIVE INSERT cout << "Testing insert over capacity..." << endl; heap.insert(25); heap.insert(100); heap.insert(54); heap.insert(44); heap.insert(26); heap.insert(3); heap.insert(48); heap.insert(9); // GETMIN AFTER EXCESSIVE INSERT cout << "Testing getMin..." << endl; assert(heap.getMin() == 2); //IF THERE ARE TWO EQUAL CHILDREN NODES THAT ARE SMALLER THAN THE PARENT, SWAP ANY OF THEM cout << "Removing all the elements from the heap..." << endl; heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); assert(heap.getMin() == -1); heap.insert(3); heap.insert(6); heap.insert(6); heap.insert(8); heap.deleteMin(); cout << "Testing percolate down If there are two equal children nodes that are smaller than the parent... " << endl; assert(heap.getMin() == 6); cout << endl << "Congrats! Your Heap implementation passed all the tests!" << endl; cout << "Now you can use your implementation to complete Homework 3;" << endl; cout << "copy the files BinaryHeap.h and BinaryHeap.cpp to extend Homework 1..." << endl; return 0; } 

class BinaryHeap { public: BinaryHeap(int); // constructor that takes the capacity of the structure ~BinaryHeap(); // destructor void insert(int); // inserts a new element to the heap void deleteMin(); // removes the minimum element from the heap int getMin(); // returns the minimum element int the heap, returns -1 if the heap is empty private: int *heap; // array to store the elements of the heap int size; // keeps the number of elements in the heap int capacity; // keeps the total capacity of the heap void percolateDown(int); void percolateUp(int); void swap(int, int); }; BinaryHeap::BinaryHeap(int capacity) { this->capacity = capacity; heap = new int[capacity+1]; size = 0; } BinaryHeap::~BinaryHeap() { delete [] heap; } void BinaryHeap::insert(int element) { if (size < capacity) { size++; heap[size] = element; percolateUp(size); } else return; } void BinaryHeap::deleteMin() { if (size < 1) return; else { heap[1] = heap[size]; size--; percolateDown(1); } } int BinaryHeap::getMin() { if (size < 1) return -1; else return heap[1]; } void BinaryHeap::percolateDown(int hole) { int leftChildIndex, rightChildIndex, minIndex; leftChildIndex = hole * 2; rightChildIndex = hole * 2 + 1; if (rightChildIndex >= size) { if (leftChildIndex >= size) return; else minIndex = leftChildIndex; } else { if (heap[leftChildIndex] <= heap[rightChildIndex]) minIndex = leftChildIndex; else minIndex = rightChildIndex; } if (heap[hole] > heap[minIndex]) { swap(hole, minIndex); percolateDown(minIndex); } } void BinaryHeap::percolateUp(int index) { int parentIndex(1); if (index != 1) { parentIndex = index / 2; } if (heap[parentIndex] > heap[index]) { swap(parentIndex, index); percolateUp(parentIndex); } } void BinaryHeap::swap(int i, int j) { int t = heap[i]; heap[i] = heap[j]; heap[j] = t; } 

The following is the main function for testing:

#include <iostream> #include <cassert> #include "BinaryHeap.h" using namespace std; int main () { cout << "Testing your heap implementation..." << endl << endl; BinaryHeap heap(10); // BASICS cout << "Testing insert for a single item..." << endl; heap.insert(3); assert(heap.getMin() == 3); heap.deleteMin(); // INSERT cout << "Testing insert..." << endl; heap.insert(5); heap.insert(10); heap.insert(4); heap.insert(2); heap.insert(56); heap.insert(34); // GETMIN cout << "Testing getMin..." << endl; assert(heap.getMin() == 2); // DELETEMIN cout << "Testing deleteMin..." << endl; heap.deleteMin(); heap.deleteMin(); // GETMIN AFTER DELETEMIN cout << "Testing getMin after deleteMin..." << endl; assert(heap.getMin() == 5); // EXCESSIVE DELETEMIN cout << "Testing deleteMin on an empty heap..." << endl; heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); // GETMIN AFTER EXCESSIVE DELETEMIN cout << "Testing deleteMin on an empty heap..." << endl; assert(heap.getMin() == -1); //IF THERE ARE TWO CHILDREN NODES THAT ARE BOTH SMALLER THAN THE PARENT, SWAP SMALLER cout << "Testing percolate down If there are two children nodes that are both smaller than the parent... " << endl; heap.insert(23); heap.insert(43); heap.insert(234); heap.insert(321); heap.insert(243); cout << "Testing percolate down If there are two children nodes that are both smaller than the parent..." << endl; assert(heap.getMin() == 23); heap.deleteMin(); assert(heap.getMin() == 43); heap.deleteMin(); assert(heap.getMin() == 234); heap.deleteMin(); assert(heap.getMin() == 243); heap.deleteMin(); assert(heap.getMin() == 321); heap.deleteMin(); // DUPLICATE ELEMENTS cout << "Testing insert with duplicate values..." << endl; heap.insert(5); heap.insert(10); heap.insert(4); heap.insert(4); heap.insert(2); heap.insert(56); heap.insert(10); heap.insert(34); // GETMIN WITH DUPLICATE ELEMENTS cout << "Testing getMin..." << endl; assert(heap.getMin() == 2); // EXCESSIVE INSERT cout << "Testing insert over capacity..." << endl; heap.insert(25); heap.insert(100); heap.insert(54); heap.insert(44); heap.insert(26); heap.insert(3); heap.insert(48); heap.insert(9); // GETMIN AFTER EXCESSIVE INSERT cout << "Testing getMin..." << endl; assert(heap.getMin() == 2); //IF THERE ARE TWO EQUAL CHILDREN NODES THAT ARE SMALLER THAN THE PARENT, SWAP ANY OF THEM cout << "Removing all the elements from the heap..." << endl; heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); heap.deleteMin(); assert(heap.getMin() == -1); heap.insert(3); heap.insert(6); heap.insert(6); heap.insert(8); heap.deleteMin(); cout << "Testing percolate down If there are two equal children nodes that are smaller than the parent... " << endl; assert(heap.getMin() == 6); cout << endl << "Congrats! Your Heap implementation passed all the tests!" << endl; cout << "Now you can use your implementation to complete Homework 3;" << endl; cout << "copy the files BinaryHeap.h and BinaryHeap.cpp to extend Homework 1..." << endl; return 0; } 

I am trying to implement an array-based, fixed-size minimum binary heap ADT. As I was testing my program, all the functions I wrote seem to work fine except for finding the minimum element which is only supposed to return the integer value stored at the root node. The root node in this implementation is placed at index 1. The error I keep getting is the read-access violation. The following is the Binary Heap class definition and the implementation of the find minimum function:

class BinaryHeap { public: BinaryHeap(int); // constructor that takes the capacity of the structure ~BinaryHeap(); // destructor void insert(int); // inserts a new element to the heap void deleteMin(); // removes the minimum element from the heap int getMin(); // returns the minimum element int the heap, returns -1 if the heap is empty private: int *heap; // array to store the elements of the heap int size; // keeps the number of elements in the heap int capacity; // keeps the total capacity of the heap void percolateDown(int); void percolateUp(int); void swap(int, int); }; int BinaryHeap::getMin() { if (size < 1) return -1; return heap[1]; } 

I am trying to implement an array-based, fixed-size minimum binary heap ADT. As I was testing my program, all the functions I wrote seem to work fine except for finding the minimum element which is only supposed to return the integer value stored at the root node. The root node in this implementation is placed at index 1. The error I keep getting is the read-access violation. The following is the Binary Heap class definition and the implementation of the functions:

class BinaryHeap { public: BinaryHeap(int); // constructor that takes the capacity of the structure ~BinaryHeap(); // destructor void insert(int); // inserts a new element to the heap void deleteMin(); // removes the minimum element from the heap int getMin(); // returns the minimum element int the heap, returns -1 if the heap is empty private: int *heap; // array to store the elements of the heap int size; // keeps the number of elements in the heap int capacity; // keeps the total capacity of the heap void percolateDown(int); void percolateUp(int); void swap(int, int); };   BinaryHeap::BinaryHeap(int capacity) { this->capacity = capacity; heap = new int[capacity+1];  size = 0; } BinaryHeap::~BinaryHeap() { delete [] heap; } void BinaryHeap::insert(int element) {  if (size < capacity) {  size++; heap[size] = element; percolateUp(size); } else return; } void BinaryHeap::deleteMin() { if (size < 1)    return; else {  heap[1] = heap[size]; size--; percolateDown(1); } } int BinaryHeap::getMin() { if (size < 1) return -1;   else return heap[1]; }  void BinaryHeap::percolateDown(int hole) { int leftChildIndex, rightChildIndex, minIndex; leftChildIndex = hole * 2; rightChildIndex = hole * 2 + 1;  if (rightChildIndex >= size) { if (leftChildIndex >= size) return; else minIndex = leftChildIndex; } else { if (heap[leftChildIndex] <= heap[rightChildIndex]) minIndex = leftChildIndex; else minIndex = rightChildIndex; } if (heap[hole] > heap[minIndex]) { swap(heap[hole], heap[minIndex]); percolateDown(minIndex); } } void BinaryHeap::percolateUp(int index) { int parentIndex(1); if (index != 1) { parentIndex = index / 2; } if (heap[parentIndex] > heap[index]) { swap(heap[parentIndex], heap[index]); percolateUp(parentIndex); } } void BinaryHeap::swap(int i, int j) { int t = heap[i]; heap[i] = heap[j]; heap[j] = t; }