How do I access minimum element using array-based binary heap?

Question

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(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; }

I am trying to implement an array-based, fixed size minimum binary heap ADT -- Is there a reason why you're not using the ready-made heap functions? — PaulMcKenzie
– PaulMcKenzie, Commented Nov 13, 2019 at 17:38
it is because it makes it easier to access children/parent indexes using leftchild=index*2, rightchild=index*2+1 and parent=index/2. - -So your professor is trying to fit a square peg into a round hole. C++ starts arrays at 0, not 1. By faking a 1-based array, you are at risk of either falling of the right edge, causing a memory access error, or erroneously accessing element 0, resulting in wrong calculations. Believe me, I've seen this hundreds of times before, where the coder is trying this and then wind up with these issues. — PaulMcKenzie
– PaulMcKenzie, Commented Nov 13, 2019 at 18:52
Relevant: stackoverflow.com/a/49806133/56778. I think your instructor should read this. Also stackoverflow.com/a/22900767/56778 — Jim Mischel
– Jim Mischel, Commented Nov 14, 2019 at 0:06

Jim Mischel · Accepted Answer · 2019-12-03 21:18:00Z

There is a bug in your percolateDown function.

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); } }

Let's assume you have 4 items in your heap. Visually, it looks like this:

 1 / \ 3 2 / 4

The array, since you start your heap at 1, would contain [0,1,3,2,4], and size is 4. You call deleteMin, which moves the last item to the front, giving you [0,4,3,2,4], with size = 3. Then it calls percolateDown(1).

percolateDown computes leftChildIndex = 2 and rightChildIndex = 3. Then you hit this:

`if (rightChildIndex >= size)`

But rightChildIndex is equal to 3, which is the same as size. So the code will never enter the conditional to compare the right child with the left child. Instead, it will compare the left child with the parent, find that it's less, and swap the nodes. You will end up with this invalid heap:

 3 / \ 4 2

It's interesting to note that the >= check on the indexes is a common idiom when dealing with 0-based arrays. But the code you're working with treats the array as though it's 1-based. And with 1-based arrays the standard idiom is >. This is one of the reasons I strongly recommend putting the root node of a binary heap at 0 when you're working with a language that has 0-based arrays.

A cleaner (and correct) way to do this would be:

 int leftChildIndex, rightChildIndex, minIndex; leftChildIndex = hole * 2; rightChildIndex = hole * 2 + 1; if (leftChildIndex > size) { // if the left child index is outside the heap, // then the right child index will be, too. return; } // assume left is smallest minIndex = leftChildIndex; // and only check the right if it exists if (rightChildIndex <= size) { if (heap[rightChildIndex] < heap[leftChildIndex]) { minIndex = rightChildIndex; } }

Collectives™ on Stack Overflow

How do I access minimum element using array-based binary heap?

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related