Реализация очереди приоритетов

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. Возврат 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 ++.

Answer 2

Как вы думаете, что делает этот код?if (q[0] == NULL) эквивалентно if (q[0] == 0).Значения, которые вы вводите, никогда не равны 0?Кроме того, несмотря ни на что, ваша первая функция никогда не вернет FAILURE.Код, который вы написали, вообще не реализует функциональность приоритетной очереди.Прочитайте CLRS (https://www.amazon.ca/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844) и выполните это на более простом языке (например, Python).