实现优先队列

Question

我正在尝试为主队列实现插入、查找最小值和删除最小值功能。我还进行了测试，通过将代码与另一个队列一起检查来确保我的代码正常工作。出于某种原因，当使用查找最小值和删除最小值函数时，它带有与其他队列不同的值。我该如何解决这个问题？

#include "pQueue.h"
#include <iostream>
using namespace tom;

status pQueue::insert(int insertInt)
{

    if (q[0] == NULL)
    {
        q[0] = insertInt;
        minimum = insertInt;
    }
    else if (q[0] != NULL)
    {
        q[count] = insertInt;
    }
    else
    {
        return FAILURE;
    }

    if (insertInt < minimum)
    {
        minimum = insertInt;
    }
    return SUCCESS;
    count++;

}

status pQueue::findMin(int &minElement)
{

    minElement = minimum;

    if (minElement == NULL)
    {
        return FAILURE;
    }
    return SUCCESS;
}

status pQueue::deleteMin()
{

    for (int i = 0; i <= count; i++)
    {
        if (q[i] = minimum)
        {
            q[i] = 0;
        }
        if (q[i] != 0)
        {
            return FAILURE;
        }

    }
}

Answer 1

您认为这段代码在做什么？ if (q[0] == NULL) 等同于 if (q[0] == 0)。您插入的值永远不会为 0 吗？此外，无论如何，您的第一个功能永远不会 return 失败。您编写的代码根本没有实现优先级队列功能。阅读 CLRS(https://www.amazon.ca/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844) 并首先用更简单的语言（如 Python）实现它。

Answer 2

假设您将其存储在数组中，未排序优先级队列的一般思路是：

插入：

将项目添加为数组中的最后一项。
递增count.

移除：

扫描数组以找到最小项的索引。
将该索引中的值复制到名为 result
将数组中的最后一个值复制到该位置
递减 count.
Return result

所以插入变成（伪代码）

insert(value)
    a[count] = value
    count = count + 1

deleteMin 是：

deleteMin()
    minIndex = findMinIndex()
    result = a[minIndex]
    a[minIndex] = a[count-1]
    count = count - 1
    return result

findMinIndex 是：

findMinIndex()
    if (count < 1) then error
    minIndex = 0
    for (i = 1; i < count; ++i)
        if (a[i] < a[minIndex])
            minIndex = i
    return minIndex

而 findMin 是：

findMinIndex()
    return a[findMinIndex()]

我会把 C++ 实现留给你。

实现优先队列

Implementing Priority Queue

c++

queue

traversal

priority-queue