在C++中实现优先队列

Question

在C++中实现优先队列

3

我正在尝试使用循环数组实现队列。我的代码应该能够从队列中删除最小的数字。我创建了测试代码，应该输出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;
}

- JosephK

2

从extractMin()返回array[front]而不是minValue，这个说法正确吗？ - 4pie0

错过了那个。谢谢你发现了它。 - JosephK

注意：你的队列有问题，如果你尝试复制它，你可能会遇到崩溃。不要使用“new”，而是尝试使用std::vector<int>; 然后你可以删除你编写的析构函数，因为它将变得无用。一般来说，我建议你不要混合职责：一个类处理内存，一个类处理逻辑，这样两个类都会简单（并且可以独立测试）。 - Matthieu M.

2个回答

1

假设您修复了这个小问题：

//return smallest value
    return array[front];

你返回的是队列的前面而不是最小元素，这仍然存在代码问题，因为它的行为很奇怪（对于队列来说）：假设你的队列大小为4，并且你有元素3 1 2 4在队列中，按照这个顺序。当你提取时，你会返回1，现在如果你插入一个新元素5，你的队列将包含5,1,2,4；所以你覆盖了错误的元素。

- Pandrei

哦，好的。这样想象确实有帮助。谢谢。 - JosephK

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Simon Karlsson · Accepted Answer

你找到了最小值，但在提取最小值时，它并不是你返回的值。

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

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

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

我建议在插入时进行上述更改，并将您的extractmin更改为以下内容：

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

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