## Introduction

Regular queue follows a First In First Out (FIFO) order to insert and remove an item. Whatever goes in first, comes out first. However, in a priority queue, an item with the highest priority comes out first. Therefore, the FIFO pattern is no longer valid.

Every item in the priority queue is associated with a priority. It does not matter in which order we insert the items in the queue, the item with higher priority must be removed before the item with the lower priority. If the two items have same priorities, the order of removal is undefined and it depends upon the implementation.

The real world example of a priority queue would be a line in a bank where there is a special privilege for disabled and old people. The disabled people have the highest priority followed by elderly people and the normal person has the lowest priority.

## Operations on a priority queue

Just like the regular queue, priority queue as an abstract data type has following operations.

**EnQueue**: EnQueue operation inserts an item into the queue. The item can be inserted at the end of the queue or at the front of the queue or at the middle. The item must have a priority.**DeQueue**: DeQueue operation removes the item with the highest priority from the queue.**Peek**: Peek operation reads the item with the highest priority.

The complexity of these operation depends upon the underlying data structure being used.

## Implementation

A priority queue can be implemented using data structures like arrays, linked lists, or heaps. The array can be ordered or unordered.

### Using an ordered array

The item is inserted in such a way that the array remains ordered i.e. the largest item is always in the end. The insertion operation is illustrated in figure 1.

The item with priority 7 is inserted between the items with priorities 6 and 8. We can insert it at the end of the queue. If we do so the array becomes unordered. Since we must scan through the queue in order to find the appropriate position to insert the new item, the worst-case complexity of this operation is O(n). Since the item with the highest priority is always in the last position, the dequeue and peek operation takes a constant time. The C program below implements the enqueue and dequeue operation using an ordered array.

1 | // insert an item at the appropriate position of the |

### Using an unordered array

We insert the item at the end of the queue. While inserting, we do not maintain the order. The complexity of this operation is O(1). Since the queue is not ordered, we need to search through the queue for the item with maximum priority. Once we remove this item, we need to move all the items after it one step to the left. The dequeue operation is illustrated in figure 2.

It is obvious that the complexity of dequeue and peek operation is O(n). The following C program implements the priority queue using an unordered array.

1 | // insert an item at the rear of the queue |

### Using a linked list

The linked can be ordered or unordered just like the array. In the ordered linked list, we can insert item so that the items are sorted and the maximum item is always at the end (pointed by head or tail). The complexity of enqueue operation is O(n) and dequeue and peek operation is O(1).

In an unordered linked list, we can insert the item at the end of the queue in constant time. The dequeue operation takes linear time (O(n)) because we need to search through the queue in order to find the item with maximum priority.

### Using a binary heap

In above implementations using arrays and linked lists, one operation always takes linear time i.e. O(n). Using binary heaps, we can make all the operations faster (in logarithmic time). Please read about the binary heaps before using them in a priority queue.

Using a binary heap, the enqueue operation is insert operation in the heap. It takes O(log n) time in the worst case. Similarly, the dequeue operation is the extract-max or remove-max operation which also takes O(log n) time. The peek operation is a constant time operation. In this way, the binary heap makes the priority queue operations a way faster.

The C, C++, and Java implementation of a priority queue using the binary heap is given below.

1 | // C implementation of a max priority queue |

1 | // C++ implementation of a priority queue |

1 | // Java implementation of a max priority queue |

## Complexity

The complexity of the operations of a priority queue using arrays, linked list, and the binary heap is given in the table below.

Data Structure | EnQueue | DeQueue | Peek |
---|---|---|---|

Ordered Array | O(n) | O(1) | O(1) |

Unordered Array | O(1) | O(n) | O(n) |

Ordered Linked List | O(n) | O(1) | O(1) |

Unordered Linked List | O(1) | O(n) | O(n) |

Binary Heap | O(log n) | O(log n) | O(1) |