Implementing priority queue in C++

Question

I am trying to implement a queue using a circular array. My code is supposed to be able to remove the lowest number from the queue. I created test code that should output 1 2 3 4 5 as the lowest values being removed but my actual output is 3 2 1 8 7. I am not sure if my problem is that my code for finding the lowest value is incorrect or there is a problem with how i am coding the actual queue. I suspect both but I'd appreciate any suggestions or tips to finding the problems in my code.

#include <iostream>
using namespace std;

class priorityQueue
{
private:
    int front;
    int rear;
    int size;
    int *array;

public:
    priorityQueue();
    ~priorityQueue();
    void insert(int x);
    //remove and return the smallest item currently in the priority queue
    int extractMin();
    bool empty();
};

priorityQueue::priorityQueue()
{
    front = rear = -1;
    size = 10;
    array = new int[size];
}

priorityQueue::~priorityQueue()
{
    delete[] array;
}

void priorityQueue::insert(int x)
{
    //if queue is full
    if ( (rear + 1)% size == front ){
        return;
    }

    //else if queue is empty
    else if ( empty() ){
        rear = front = 0;
    }

    else
    {
        rear = (rear + 1) % size;
    }

    array[rear] = x;
}

//extract and return smallest value in queue
int priorityQueue::extractMin()
{
    int minValue = array[front];

    if ( empty() ){
        return -1;
    }

    else if (front == rear){
        front = rear = -1;
        }

    else
    {
        front = (front + 1) % size;
    }

    //find smallest value
    for (int i = front; i <= rear; i++){
        if (array[i] < minValue)
            minValue = array[i];
    }

    //return smallest value
    return array[front];
}

bool priorityQueue::empty()
{
    if ( (front == -1) && (rear == -1) )
        return true;
    else
        return false;
}

int main()
{
    priorityQueue myqueue;

    myqueue.insert(4);
    myqueue.insert(3);
    myqueue.insert(2);
    myqueue.insert(1);

    cout << myqueue.extractMin() << endl;
    cout << myqueue.extractMin() << endl;

    myqueue.insert(8);
    myqueue.insert(7);
    myqueue.insert(6);
    myqueue.insert(5);

    cout << myqueue.extractMin() << endl;
    cout << myqueue.extractMin() << endl;
    cout << myqueue.extractMin() << endl;

    system("pause");
    return 0;
}

Solution 1

You do find the smallest value however it is not the value that you return when you extract min:

//find smallest value
for (int i = front; i <= rear; i++){
    if (array[i] < minValue)
        minValue = array[i];
}

//return smallest value
return array[front]; //Not equal to the smallest value

I think that what you want to do is find the smallest number then remove it from the array and return it.

This is maybe not the most clean solution but it will solve your problem:

int minIndex = front;

//find smallest value
for (int i = front; i <= rear; i++){
    if (array[i] < minValue)
    {
        minIndex = i;
        minValue = array[i];
    }
}

array[minIndex] = array[front];

//return smallest value
return minValue;

If i were to implement a priority queue i would ensure to allways put the smallest value at front and make sure that the array is sorted when i do insert.

int index = rear;

for(int i = front ; i <= rear ; i++)
{
    if(x < array[i])
    {
        for(int j = rear ; j >= i ; j--)
        {
            array[j] = array[j-1];
        }
        index = i;
        break;
    }
}

array[index] = x;

Adding this to your insert would sort of work however first time when the following snippet is run front will be set to one. which means you will skip the first value in the queue.

else
{
    front = (front+1) % size;
}

I would suggest making the above change in insert and change your extractmin to something like this:

//extract and return smallest value in queue
int priorityQueue::extractMin()
{
    //Handle circulation.

    //return smallest value
    return array[front++];
}

Solution 2

assuming you fix this small issue:

//return smallest value
    return array[front];

where you are returning the front of the queue not the smallest element,

you still have a problem in your code because it's behaving strange (for a queue): suppose your queue size is 4 and you have elements 3 1 2 4 int the queue; in that order. When you extract, you return 1, and now if you insert a new element, 5, your queue will contain 5,1,2,4; So you overwrote the wrong element;

Comments

[JosephK]

i was thinking return[front] or return[minValue] (which i saw to be wrong) and i was oblivious to return minValue. my new output for that is 1 1 1 1 5. It starts and ends well so that's a plus. : ) I'll keep at it.

[JosephK]

Oh, okay. Visualizing it like that helps out. Thanks.

[JosephK]

I adjusted my code to include minIndex like you suggested but my output is 1 2 2 3 5. Is that an error on my end. Were you able to come up with the correct output?

[JosephK]

Oh, okay. Just checking. Thanks.