Реализация очереди приоритетов в 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

Вы делаете найти наименьшее значение, однако это не значение, которое вы возвращаете при извлечении мин:

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

Если я должны были реализовать приоритетную очередь я бы обеспечить, чтобы Allways поставить наименьшее значение на передней и убедитесь, что массив сортируется, когда я вставляю.

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

Я бы предложил сделать вышеуказанное изменение вставки и изменить extractmin на что-то вроде этого:

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

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

Answer 2

если вы решить эту небольшую проблему:

//return smallest value 
    return array[front]; 

где вы возвращаете фронт очереди не самый маленький элемент,

у вас все еще есть проблема i n ваш код, потому что он ведет себя странно (для очереди): предположим, что размер вашей очереди равен 4, и у вас есть элементы 3 1 2 4 int queue; в этой последовательности. Когда вы извлекаете, вы возвращаете 1, и теперь, если вы вставляете новый элемент, 5, ваша очередь будет содержать 5,1,2,4; Таким образом, вы перезаписываете неправильный элемент;