c++ - C++中优先队列的实现

Question

我正在尝试使用循环数组实现队列。我的代码应该能够从队列中删除最小的数字。我创建的测试代码应该输出 1 2 3 4 5 作为被删除的最低值，但我的实际输出是 3 2 1 8 7。我不确定我的问题是我的查找最低值的代码不正确还是有我如何编码实际队列的问题。我怀疑两者都有，但如果有任何建议或提示可以帮助我找到代码中的问题，我将不胜感激。

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

Answer 1

您确实找到了最小值，但它不是您提取 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

我认为您想要做的是找到最小的数字，然后将其从数组中删除并返回。

这可能不是最干净的解决方案，但它会解决您的问题:

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;

如果我要实现一个优先级队列，我会确保始终将最小值放在前面，并确保在插入时对数组进行排序。

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;

将此添加到您的插入中会有点工作，但是第一次运行以下代码段时，前面将设置为一个。这意味着您将跳过队列中的第一个值。

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

我建议在 insert 中进行上述更改，并将 extractmin 更改为如下所示:

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

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