c++ - 实现优先队列

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

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

插入:

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

删除:

1. 扫描数组以找到最小项的索引。
2. 将该索引中的值复制到名为 result 的变量中
3. 将数组中的最后一个值复制到该位置
4. 减少 count。
5. 返回结果

所以插入变成(在伪代码中)

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++ 实现留给您。