0

I'm currently struggling with an assignment involving the implementation of a priority queue using a binary min-heap. The user inserts values upon startup, and then has the options to insert more values, delete the minimum value, or print the priority queue. I have everything implemented, except that I can't seem to correctly implement my insertion function.

My code for the implementation file:

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

using namespace std;

PriorityQueue::PriorityQueue():arrSize(100), currentSize(0){
  arr = new int[arrSize];
  for(int i = 0; i <= arrSize; i++){
    arr[i] = 0;
  }
}

bool PriorityQueue::isEmpty(){
  if (currentSize == 0){
    return true;
  }
  else {
    return false;
  }
}

void PriorityQueue::insert(int value){
  currentSize++;
  int index = currentSize;
  arr[index] = value;
  int parent=(index-1)/2;
  while(index !=0 && arr[parent]>arr[index]){
    int temp = arr[index];
    arr[index]=arr[parent];
    arr[parent] = temp;
    index=parent;
  }
}

int PriorityQueue::deleteMin(){
  int min = arr[1];
  arr[1] = arr[currentSize];
  currentSize--;
  percolateDown(1);
  return min;
}

void PriorityQueue::printQueue(){
  for (int i = 1; i < currentSize+1; i++){
    cout << arr[i] << " ";
  }
  cout << endl;
}

void PriorityQueue::percolateDown(int hole){
  int minIndex = hole;
  int left = (2*hole);
  int right = (2*hole)+1;

  if (left <= currentSize && arr[left] < arr[minIndex]){
    minIndex = left;
  }

  if (right <= currentSize && arr[right] < arr[minIndex]){
    minIndex = right;

  }

  if(minIndex != hole){
      int temp = arr[hole];
      arr[hole] = arr[minIndex];
      arr[minIndex] = temp;
    }
}

For example, if I insert 100 70 50 125 45 60 10, it will return 50 45 10 125 70 60 100 instead of 10 50 45 125 100 70 60. Occasionally, the queue will be correctly ordered. I notice that it almost always fails to put the minimum value in the correct place.

Edit: Changing the for loop statement in printQueue() to start at 0 instead of 1 doesn't change the output apart from adding an arbitrary 0. I've changed i <= currentSize to i < currentSize+1. Currently debugging.

hadcol
  • 1
  • 1
  • 2
    *I have everything implemented, except that I can't seem to correctly implement my insertion function.* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – PaulMcKenzie Apr 28 '23 at 20:46
  • 1
    `for (int i = 1; i <= currentSize; i++)` -- In C++, arrays and indexing start at 0, not 1. Writing code that tries to fake C++ into starting at 1 has a very good chance of being off-by-one somewhere, either at the left end (accessing element 0 when you didn't mean to do this), or on the right end (accessing an element out-of-bounds). – PaulMcKenzie Apr 28 '23 at 20:51
  • Extending the above comment, any time you see a `<=` in a loop exit condition you should stop and read the loop more closely. You're probably looking at a bug. – user4581301 Apr 28 '23 at 21:13
  • You have to decide whether you want the first item in your queue to be at `arr[0]` or at `arr[1]`. In your `insert` method you have `int parent=(index-1)/2;`, which is the calculation if you have a 0-based queue. But in your `deletMin` you treat it as though the root is at `arr[1]`. Either will work, but you have to pick one or the other. – Jim Mischel May 03 '23 at 12:58

0 Answers0