Priority Queue Implementation using unordered Array in C++

Array implementation can be the preferred choice for Priority Queue when the data is limited in size. In an unordered Array, the elements are always enqueued at the Rear side. So, prefer the unordered array implementation for applications that require faster insertion.

• See Priority Queue Implementation using ordered Array to perform faster retrieval.
• Alternatively, see Priority Queue Implementation using Linked List to work with large and dynamic data.

1. Representation

Each element in the Array includes the data and priority associated with it. We do not need the Front pointer for Priority Queues since we need to remove the high-priority element always.

2. Priority Queue Implementation using unordered Array

An example program to implement the Priority Queue using an unordered Array. This object-oriented implementation encapsulates the Priority Queue data structure using a c++ class.

/**
 * C++ example to demonstrate Priority Queue implementation using unordered Array
 */
#include <iostream>
using namespace std;

// Queue maximum capacity
#define CAPACITY 8

/**
 * Priority Queue Element
 */
struct Element
{
    int value;
    int priority;
    
    Element() : value(-1), priority(-1) {}
    Element(int v, int p) : value(v), priority(p) {}
};

/**
 * Priorty Queue implementation using unordered Array
 */
class PriorityQueue
{
private:
    // Queue
    Element queue[CAPACITY];
    
    // Rear position
    int rear;
    
public:
    // Constructor
    PriorityQueue() : rear(-1) {}

    // Enqueue new element to the Queue
    void enqueue(Element element);

    // Dequeue the element from Queue
    Element dequeue();

    // Returns the high priority element without deleting it
    Element peek();

    // Print the Queue
    void display(string msg);

    // Check if the Queue is empty
    bool isEmpty();

    // Check if the Queue is full
    bool isFull();

    // Search the high priority element from Queue
    int getHighPriorityPos();
};

// Enqueue new element to the Queue
void PriorityQueue::enqueue(Element element) {
    // Step 1. Return if the Queue is full, proceed otherwise
    if (isFull()) {
        return;
    }
    
    // Step 2. Move the Rear to next position
    rear++;
    
    // Step 3. Insert the new element at Rear
    queue[rear] = element;
}

// Dequeue the element from Queue
Element PriorityQueue::dequeue() {
    // Step 1. Return if the Queue is empty, proceed otherwise
    if (isEmpty()) {
        throw runtime_error("Queue is Empty");
    }
        
    // Step 2. Find and Retrieve the next high priority element
    int pos = getHighPriorityPos();
    Element element = queue[pos];

    // Step 3. Replace the high priority element with the Rear element
    // (or) Shift elements if you want to preserve the original order
    queue[pos] = queue[rear];
    
    // Step 4. Move Rear to previous position
    rear--;
    
    return element;
}

// Returns the high priority element without deleting it
Element PriorityQueue::peek() {
    if (isEmpty()) {
        throw runtime_error("Queue is Empty");
    }
    int pos = getHighPriorityPos();
    return queue[pos];
}

// Print the Queue
void PriorityQueue::display(string msg) {
    cout << msg << endl;
    if (isEmpty()) {
        return;
    }
    
    for (int i=0; i < rear; i++) {
        cout << queue[i].value << " (" << queue[i].priority << ")" << endl;
    }
    cout << queue[rear].value << " (" << queue[rear].priority << ") <-- rear" << endl;
}

// Check if the Queue is empty
bool PriorityQueue::isEmpty() {
    if (rear == -1) {
        return true;
    }
    return false;
}

// Check if the Queue is full
bool PriorityQueue::isFull() {
    if (rear == (CAPACITY-1)) {
        return true;
    }
    return false;
}

// Search the high priority element from Queue
int PriorityQueue::getHighPriorityPos() {
    if (isEmpty()) {
        return -1;
    }
    
    int pos = 0;
    int highPriority = queue[pos].priority;
    for (int i=1; i <= rear; i++) {
        if (highPriority > queue[i].priority) {
            pos = i;
            highPriority = queue[i].priority;
        }
    }
    return pos;
}

// The main function to begin the execution
int main()
{
    // Create a Queue
    PriorityQueue queue;
    
    // Enqueue elements (10, 20, and 30)
    queue.enqueue(Element(10, 3));
    queue.enqueue(Element(20, 1));
    queue.enqueue(Element(30, 2));
    queue.display("Queue after inserting 10 (3), 20 (1), and 30 (2)");
    
    // Get the peek element
    Element element = queue.peek();
    cout << "Peek element returned " << element.value << endl;
    
    // Dequeue the elements from Queue
    element = queue.dequeue();
    cout << "Dequeue element returned " << element.value << endl;
    element = queue.dequeue();
    cout << "Dequeue element returned " << element.value << endl;
    queue.display("Queue after removing two elements");
}

Output

Queue after inserting 10 (3), 20 (1), and 30 (2)
10 (3)
20 (1)
30 (2) <-- rear
Peek element returned 20
Dequeue element returned 20
Dequeue element returned 30
Queue after removing two elements
10 (3) <-- rear

3. Operations of Priority Queue

Here, we discuss the operations of Priority Queue with an unsorted Array.

3.1. Enqueue with unordered Array

The enqueue works simply by inserting the new elements on the Rear side.

Algorithm

1. Return if the Queue is full, proceed otherwise.
2. Move the Rear to the next position
3. Insert the new element at the Rear

Examples

Let’s consider the following empty queue. Initially, the Rear position is set to -1.

Firstly enqueue (10) with priority (3). Since the queue is empty, insert this element to index 0 and set the Rear to 0.

Next, enqueue (20) with priority (1). Insert the subsequent elements always at the Rear side until the Queue is full.

3.2. Dequeue with unordered Array

Dequeue works by removing an element with high priority. Since the queue is unsorted, we need to search the entire queue to locate the high-priority element.

Then, remove the element by replacing it with the last element. However, if there is a requirement to preserve the original order of elements, then shift the elements instead of replacing them.

Algorithm

1. Return if the Queue is empty, proceed otherwise
2. Find and Retrieve the next element based on priority.
3. Replace the element with the Rear element. (or) Shift elements if you want to preserve the original order
4. Move the Rear to the previous position

Examples

Let’s consider the following queue with three elements to perform Dequeue operations.

The next element is (20) based on its priority. So, remove the element by replacing it with the last one (30).

Next, element (30) has high priority. So remove it by repeating the same process.

Dequeue the last element (10) and the queue becomes empty.