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 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.putwill put the into the queue according to the order;
  2. queue.getwill 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