Priority Queue using array in C++

Introduction

In this article, we will learn about priority queue and its implementation using an array in C++.

 

First, let’s understand what do you mean by a Priority Queue?

A priority queue is an ADT(abstract data type) that processes the elements as per their priority. 

 

What is the difference between a Priority Queue and a normal queue?🤔

In a queue, the First-In-First-Out(FIFO) rule is implemented whereas, in a priority queue, the values are removed based on priority. The element with the highest priority is removed first.

 

Real-Life Scenario

You can understand the priority queue easily with a real-life scenario. Consider that there is a queue in any hospital. So, irrespective of the order of patients in the queue, the patient who is in a more critical condition will be given higher priority than others. So, the priority, in this case, is decided by the medical condition of the patients. 

Similarly, in different real-life applications, different factors control the priority of the elements being considered.

 

Types of Priority Queue

There are two types of priority queues. Each of them is useful for different use cases. Let’s see them one by one.

  • Min Priority Queue 
    As the name suggests, in Min Priority Queue, the element with minimum value gets the highest priority, and the one with maximum value gets the lowest priority.
     
  • Max Priority Queue
    It is exactly the opposite of the min priority queue. So, the element with maximum value gets the highest priority, and the one with minimum value gets the lowest priority.
     

A min priority queue can be implemented using min-heap, and a max priority queue can be implemented using max-heap.

 

Operations in a Priority Queue

A priority queue supports the following operations:

  • enqueue(): It inserts new data into the queue.
     
  • Dequeue (): It removes the data with the highest priority from the queue.
     
  • Peek ()/top(): It returns the element having the highest priority in the queue.

     

Different ways for the Implementation of Priority Queues

We can implement the priority queues in several ways. Let’s see some of the possible options - 

 

  • Unordered Array Implementation: Elements are inserted into the array without bothering the order. Deletions are performed by searching the minimum or maximum and deleting.
     
  • Unordered List Implementation: It is similar to array implementation but instead of array linked lists are used.
     
  • Ordered Array Implementation: Elements are inserted into the array in sorted order based on the key field. Deletions are performed only at one end of the array.

 

  • Ordered list implementation: Elements are inserted into the list in sorted order based on the key field. Deletions are performed at only one end, hence preserving the status of the priority queue. All other functionalities associated with a linked list ADT are performed without modification.

 

  • Binary Search Trees Implementation: Insertion and deletions are performed in a way such that the property of BST is reserved. Both the operations take O(logn) time on average and O(n) in the worst case.

 

  • Balanced Binary Search Trees Implementation: Insertion and deletions are performed such that the property of BST is reserved and the balancing factor of each node is -1, 0, or 1. Both operations take O(logn) time.

 

Comparing Implementations

 

 

Implementation of Priority Queue using array

One of the most basic ways of implementing a priority queue is using an array. 

So, every element of the array will store the following information - 

  1. Value of the element
  2. Priority of the element

 

Steps of the implementation - 

  1. We will define a structure with two members - Value and Priority.
  2. Declare an array of structure having a fixed size maxSize.
  3. Define a variable size which will determine the size of the priority queue at any instance. Initially, size=-1 indicates that the queue is empty.

 

Let’s see how to implement all the operations on a priority queue - 

  • enqueue(): To enqueue a new element, increment the size by 1. If size is less than maxSize, then initialize the arr[index] with the value and priority of the new element. If size exceeds the maxSize, then return.
     
  • dequeue(): It removes the element with the highest priority. So, define two variables index and highestPriority and iterate over the entire array elements. The variable index stores the index of the element having the highest priority so far, and the variable highestPriority stores the priority of arr[index]. 
    At the end of the iteration, since we need to delete the element with the highest priority, so left shift all the elements after the position “index” by one position and finally decrement size by 1.
     
  • peek()/top(): It just returns the element with the highest priority. So, define two variables index and highestPriority and iterate over the entire array elements. The variable index stores the index of the element having the highest priority so far and the variable highestPriority stores the priority of arr[index].  

 

Let’s see the code implementation which is very simple along with the analysis of time and space complexity in the next section.

C++ Implementation

/*C++ code to implement a priority queue using an array*/
#include <bits/stdc++.h>
using namespace std;
#define maxSize 1000

struct priorityQueueElem
{
    int value;
    int priority;
};

priorityQueueElem priotyQ[maxSize];

int size = -1;

void enqueue(int value, int priority)
{
    size++;

    if (size > maxSize)
    {
        cout << "Maximum number of elements that can be stored is exceeded\n";
        return;
    }
    priotyQ[size].value = value;
    priotyQ[size].priority = priority;
}

int peek()
{
    int highestPriority = INT_MIN;
    int index = -1;

    for (int i = 0; i <= size; i++)
    {

        if (highestPriority == priotyQ[i].priority && index > -1 && priotyQ[index].value < priotyQ[i].value)
        {
            highestPriority = priotyQ[i].priority;
            index = i;
        }
        else if (highestPriority < priotyQ[i].priority)
        {
            highestPriority = priotyQ[i].priority;
            index = i;
        }
    }

    return index;
}

void dequeue()
{
    int index = peek();
    for (int i = index; i < size; i++)
    {
        // left shift all elements by one
        priotyQ[i] = priotyQ[i + 1];
    }
    size--;
}

int main()
{
    int n = 5;
    int arr[n] = {100, 66, 54, 48, 32};
    for (int i = 0; i < n; i++)
    {
        enqueue(arr[i], arr[i]);
    }

    int index = peek();
    cout << priotyQ[index].value << endl;
    dequeue();

    index = peek();
    cout << priotyQ[index].value << endl;
    dequeue();

    index = peek();
    cout << priotyQ[index].value << endl;

    return 0;
}

 

Output

100
66
54

 

Time Complexity

  • Enqueue - O(1), as we just append the new element to the end of the array.
     
  • Dequeue - O(n), first we find the index of the highest priority element which takes O(n) time and then we shift the elements after the peek element to the left which also takes O(n) time. Hence, total time complexity becomes O(n).
     
  • Peek - O(n), as to find the element with the highest priority we need to iterate over all the elements in the array so time complexity becomes O(n).

Space Complexity 

O(n), where n is the maximum number of elements that can be stored in the priority queue.

 

Frequently Asked Questions

  1. What are some of the applications of the priority queue?
    It is used in the Huffman coding algorithm in the form of a min-heap. Dijkstra’s algorithm also uses a priority queue to find the shortest paths.
    The operating system handles interruptions with the help of a priority queue.
     
  2. What data structures can be used to implement the priority queue?
    Priority Queues can be implemented by using arrays, heaps, BST’s, and linked lists. The most efficient of them is using heaps.

     

Key Takeaways

In this article, we learnt all about priority queues. We started with an introduction followed by an example from a real-world scenario to understand better. 

In this article, we learnt the implementation using an array but there are many other ways too.
 

Now, that you know how to implement a priority queue, some of the problems you must practise to make your understanding crystal clear are- 

To learn priority queues from scratch you can check out this course on Introduction to Priority Queues.

Do check out the amazing Priority Queues & Heaps Notes in the Guided Paths section especially curated for you to learn the concepts in one of the most intuitive and practical ways.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think