# 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

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 and 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` :

1. `heapq.heappush`(, ): will push the value onto the
2. `heapq.heappop`(): will pop and return the smallest item from the
3. `heapq.heappushpop`(, ): will push an on the heap, then pop and return the smallest item from the .

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:

1. `queue.put`will put the into the queue according to the order;
2. `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')`

## Reference:

on the way to become a programmer

## More from Wangyy

on the way to become a programmer