Priority Queue Data Structure

Priority Queue

Priority Queues a type of queue data structure where an element is inserted from the back and removed from the front. The order of the elements in the priority queue depends on the priority of the elements.
Each element is associated with a priority in a priority queue. Elements with the same priority are served according to their order in the queue.

A basic queue data structure follows the First In First Out principle while in a priority queue, the elements are removed on the basis of priority. The element with the highest priority is dequeued first.

The structure of the element of the priority queue is:

class Node 
{
    int value
    int priority
}

Priority Queue Operations

Basic operations of a priority queue are :

• Insertion
• Deletion

Priority queue is implemented using heap data structure. Therefore, it is important to be aware of the heapify operation :

void heapify(vector<int> &elem, int i) 
{
  int size = elem.size();
  int largest = i;
  int lc = 2 * i + 1; // left child
  int rc = 2 * i + 2; // right child
  if (lc < size && elem[lc] > elem[largest])
    largest = lc;
  if (rc < size && elem[rc] > elem[largest])
    largest = rc;
  if (largest != i)
  {
    swap(&elem[i], &elem[largest]);
    heapify(elem, largest);
  }
}

Enqueue

Inserting an element into a priority queue.
Steps for insertion into priority queue (max-heap) :

• create a new node if there is no node.
• Insert the new node at the bottom (last node from left to right.)
  • heapify the array (convert the new tree into a heap.)

For Min Heap, modify it so that parentNode is always smaller than new node.

void enqueue(vector<int> &elem, int val) 
{
  int size = elem.size();
  if (size == 0) 
  {
    elem.push_back(val);
  } 
  else 
  {
    elem.push_back(val);
    for (int i = size/2-1; i >= 0; i--)
     {
      heapify(elem,i);
    }
  }
}

Dequeue

To delete element from a priority queue :

• Select the element to be deleted
• Swap it with the last element.
• Delete the last element.
• Heapify again

void dequeue(vector<int> &elem, int val)
 {
  int size = elem.size();
  int i;
  for (i = 0; i < size; i++) {
    if (val == elem[i])
      break;
  }
  swap(&elem[i], &elem[size - 1]);

  elem.pop_back();
  for (int i = size/2-1; i >= 0; i--) 
  {
    heapify(elem,i);
  }
}

Top or peek

// return top priority element
int top()
{
    return arr[0]   
}

Implementation of Priority Queue can also be performed using an array or a linked list. Among these data structures, implementation through heap is the most efficient.