Priority Queue Implementation using Array in C++

Array implementation can be the preferred choice for Priority Queue when the data is limited in size. In an ordered Array, the elements are sorted based on their priority. Therefore, the dequeue operation works faster to retrieve the high-priority element.

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

1. Representation

Each element includes the data and priority associated with it. The Front pointer is not required, because the Dequeue always occurs at the Rear side. The high-priority element is aligned at the Rear side to ease the deletion.

2. Priority Queue Implementation in C++

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

/**
 * C++ example to demonstrate Priority Queue implementation using ordered 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 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 Front 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();
};
    
// 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. Check if the Queue is empty
    if (isEmpty()) {
        // Step 3. If the Queue is empty, insert at position 0
        queue[0] = element;
    } else {
        // Step 4. Otherwise if the Queue is not empty, insert on its sorted position by shifting the other elements.
        // The high priority element is aligned at the Rear side to ease the deletion.
        int pos = rear;
        for (; element.priority >= queue[pos].priority && pos >= 0; pos--) {
            queue[pos+1] = queue[pos]; // Shift element
        }
        queue[pos+1] = element; // Insert the new element
    }
        
    // Step 5. Increment the Rear by one position
    rear++;
}

// 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. Retrieve the element at Rear
    Element element = queue[rear];

    // Step 3. Move Rear to the previous position
    rear--;
    
    return element;
}

// Returns the Front element without deleting it
Element PriorityQueue::peek() {
    if (isEmpty()) {
        throw runtime_error("Queue is Empty");
    }
    return queue[rear];
}

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

// The main function to begin the execution
int main()
{
    // Create a Queue
    PriorityQueue queue;
    
    // Enqueue elements (10, 20, 30, 40, and 50)
    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)
30 (2)
20 (1) <-- 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 ordered Array.

3.1. Enqueue on Priority Queue

Firstly, iterate the Queue and find the sorted position based on the priority. Then, shift the other elements to insert the new element in its position.

Algorithm

1. Return if the Queue is full, proceed otherwise
2. Check if the Queue is empty
3. Enqueue the element:
   • If the Queue is empty, insert the element at position 0
   • Otherwise, if the Queue is not empty, insert the element in its sorted position by shifting the other elements.
4. Increment the Rear by one position

Examples

The Queue is empty initially and the Rear is set to -1. The following steps illustrate enqueuing the first element to an empty Queue.

Enqueue the first element (10) with the priority (3)

The Rear points to a valid position when the queue is not empty. In such a case, we find the element’s position based on its priority and enqueue it to the position. Here, we insert the element (20) with priority (1) at the Rear side since the priority is higher. So, we don’t have to shift any elements.

Next, enqueue the element (30) with the priority (2). Insert the element between (10) and (20) since the priority falls between them.

3.2. Dequeue on Priority Queue

The Deque operation always removes an element from the Rear side. Because the array is sorted and the high-priority element is readily available at the Rear.

Algorithm

1. Return if the Queue is empty, proceed otherwise.
2. Retrieve the element at the Rear side.
3. Move the Rear to the previous position.

Examples

The queue must be non-empty to perform the Dequeue operation. Let’s consider the following queue and perform Dequeue.

Elements are sorted and the highest priority is available at the Rear. So, retrieve the element at the Rear side and update the Rear to point to the previous position.

Dequeue the next high-priority element (30)

The steps are similar to Dequeue the last element. The Rear automatically becomes -1 while deleting the last element and indicates the queue is empty.