# What is the Priority Queue?

For the linear data structure, elements are inserted/deleted in a specific order. For example, the queue follows FIFO(first-in-first-out) pattern, whereas the stack follows the FILO(first-in-last-out) pattern. In the real world, only following fixed rules will not solve problems. For instance, jobs sent to a printer are placed in a queue. If we have a really important job that’s needed immediately, we might want the job to be run as soon as the printer is available. This particular scenario needs a special kind of queue, known as a priority queue. In this post, I’ll introduce the priority queue and its functions in Python.

**Introduction**

Before we talk about the priority queue, let’s talk about **Abstract Data Type(ADT) **first.

An **abstract data type **(ADT) is a set of objects together with a set of operations. Those operations can be designed as we desired. For example, for the set ADT, we might have operations such as *add, remove, size,* and *contains. *Some ADT examples are linked lists, sets, and trees along with their operations. However, integers, doubles, booleans are just data types. The priority queue is a perfect example of ADTs. It’s designed with unique operations that can only be applied to it.

A priority queue is similar to a normal queue except that each element has a certain priority. The priority of the queue determines operation results:

- when removing elements: elements with higher priority are dequeued first
- when inserting elements: elements in the priority queue is sorted in increasing order or decreasing order

When building a priority queue, we must insert elements that are comparable. The data inserted into the priority queue will be sorted inside, whether in increasing order or decreasing order.

## Implement a priority queue in Python

In Python, there’re several ways available to implement a priority queue. For example, we can use a list to collect elements. The only difference is that we need to sort the list every time we insert/delete an element. In fact, Python provides built-in libraries for us to use. The followings are two options.

**using****heapq**

The heap is frequently used to implement a priority queue. To create a priority queue, we can simply initialize an empty list, or transform a populated list using the function `heapify()`

There are three main functions in `heapq`

:

`heapq.`

(**heappush***heap*,*item*): will push the value*item*onto the*heap;*`heapq.`

(**heappop***heap*): will pop and return the smallest item from the*heap;*`heapq.`

(**heappushpop***heap*,*item*): will push an*item*on the heap, then pop and return the smallest item from the*heap*.

Simple example:

import heapq>>> h = []

>>> heappush(h, (3, 'c'))

>>> heappush(h, (4, 'd'))

>>> heappush(h, (1, 'a'))

>>> heappush(h, (2, 'b'))#now h = [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]>>> heappop(h)

(1, 'a')>>> heappushpop(h, (5, 'e'))

(2, 'b')

**using****queue.PriorityQueue**

Similar to `heapq`

, the `queue`

module in Python can also build a priority queue. Different from the `heapq`

, `PriorityQueue`

is implemented in a classic OOP style. There are two main functions:

`queue.`

**put***(item):*will put the*item*into the queue according to the order;`queue.`

**get***()**:*will remove and return an item from the queue.

from queue import PriorityQueue>>> pq = PriorityQueue()

>>> pq.put((3, 'c'))

>>> pq.put((4, 'd'))

>>> pq.put((1, 'a'))

>>> pq.put((2, 'b'))#now pq = [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]>>> pq.get()

(1, 'a')