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

is this correct that you return array[front] not minValue from extractMin()? — 4pie0
– 4pie0, Commented Feb 10, 2014 at 8:31
Note: your queue is broken, if you try to copy it you will probably experience a crash. Instead of using new, try using std::vector<int>; you can then remove the destructor you wrote as it will be useless. In general, I advise you not to mix responsibilities: one class to handle memory, one class to handle logic, this way both are simple (and can be tested independently). — Matthieu M.
– Matthieu M., Commented Feb 10, 2014 at 10:19

Simon Karlsson · Accepted Answer · 2014-02-10 09:17:03Z

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++];
}

edited Feb 10, 2014 at 9:17

answered Feb 10, 2014 at 8:35

Simon Karlsson

4,13024 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

JosephK Over a year ago

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 Over a year ago

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 Over a year ago

Oh, okay. Just checking. Thanks.

Pandrei · Accepted Answer · 2014-02-10 08:36:35Z

1

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;

answered Feb 10, 2014 at 8:36

Pandrei

4,9443 gold badges32 silver badges44 bronze badges

1 Comment

JosephK Over a year ago

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

Collectives™ on Stack Overflow

Implementing priority queue in C++

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related