Priority Queue Explained With Simple Example

A Priority Queue is an abstract data type similar to Queue which has following properties

• Every element in the Priority Queue has a priority associated with it.
• An element with high priority will be dequeued first.
• If two element has same priority then they are dequeued based on normal Queue basis (FIFO).

Priority Queue Simple Class Implementation

Let’s have a look into the basic C++ class definition of Priority Queue.

typedef struct queue_node
{
    int m_data;
    int m_priority;
    struct queue_node* m_next;
} QueueNode;

class PriorityQueue
{
    public:
        QueueNode* m_start;
        PriorityQueue ();
        ~PriorityQueue ();
};

PriorityQueue::PriorityQueue ()
{
    m_start = NULL;
}

PriorityQueue::~PriorityQueue ()
{
    QueueNode* temp = NULL;
    while (m_start)
    {
        temp = m_start -> m_next;
        delete m_start;
        m_start = temp;
    }
}

Priority Queue Operations

Following Operations are possible in Priority Queues.

Inserting an element

In order to insert an element in Priority Queue, data should be inserted based on the element’s priority. After insertion all elements should be ordered based on the key.

Deleting an element

Since Priority Queue has all the elements ordered based on priority, hence deletion of an element happens based on highest priority element or lowest priority element.

Find Minimum/Maximum element

Since Priority Queue has all the elements ordered based on priority, hence smallest/largest elements are returned without deleting it.

Size of Priority Queue

Returns Total size of Priority Queue.

Priority Queue Implementation

Below are the possible options for Priority Queues.

unsorted array implementation

Elements are inserted in an array in normal order. In case of deletion highest/lowest priority element is searched and deleted.

sorted array implementation

Elements are inserted in sorted manner based on priority. Thus deletions can be carried from one end directly.

unsorted Linked List Implementation

Elements are inserted in an Linked List in normal order. In case of deletion highest/lowest priority element is searched and deleted.

sorted Linked List implementation

Elements are inserted in an Linked List sorted manner based on priority. Thus deletions can be carried from one end directly.

Binary Search Tree implementation

Elements are inserted in Binary Search Tree based on priority. Thus inorder provides elements in an order in which it needs to be dequeued.

Binary Heap Implementation

Elements are inserted using Heap properties. Thus, root element will always be highest/lowest priority item. Once deleted, Heap needs to be rebalanced to put highest/lowest at the root.

Priority Queue Implementation Comparison