Queues are something intrinsic to humans as when we need to do something and it’s busy you usually have to wait in a queue or line of some sort. In Python and other programming languages, queues and heaps are a way to build sequential lists of objects and a tidy way to keep them in order. For programs that are time- or sequence-dependent, queues and heaps are ideal ways to capture this type of information to flow through the required processes of the program.
What is a Priority Queue?
In Python, a priority queue is a special type of data structure that holds a collection of items with each item having a set priority assigned to it. The priority determines the sequence that it belongs to in the queue and helps maintain the order of the item within the structure. The nomenclature within Python is pqueue.
Operations to Manipulate the Priority Queue
Two fundamental concepts about priority queues are about how objects are added to the queue and there are two main methods of doing this, they are:
- Stack – (LIFO) or Last In, First Out and a simpler way of thinking about how stacking works is just as the name implies. If you stack blocks one on top of the other in a ‘queue’ of stacked blocks, then when it comes to removing a block from that stack it will always be the last one entered.
- Queue – (FIFO) First In, First Out is more aligned to the concept of queues that we humans are more accustomed to. Essentially as a queue is built, the next person in the queue goes to the back of the line and the person in the first spot is processed and removed from the queue.
There are a couple of different operations that are used to manipulate the way items are captured, removed, and sequenced within a priority queue. The three primary operations are Insert, delMax/Min, and findMax/Min. In actuality, there are 5 operations, but the del and find operations behave in the same manner while performing the operation at either end of the spectrum.
Insert – This is a simple operation and it essentially inserts items in the priority queue
delMax/Min – This operation also looks to remove an item from the queue that exists on one end of the spectrum, depending on the structure of the queue (either a stack or queue as shown above).
findMax/Min – To understand the items in the queue it may be necessary to know what the bookend objects of a queue are and findMax/Min will do that.
Use Cases for Priority Queues:
Event-Driven Simulation – As mentioned before, if time is a variable that you want to capture within a sequence, then using a queue to denote where things belong is an ideal way to programmatically construct it.
Numerical Computation – A more "boring" side of coding but looking at how to minimize the errors associated with rounding off can be done utilizing priority queues. Understanding the significant figures of given measurements and reducing the error that is introduced by rounding errors can be minimized.
Data Compression – Trying to find ways to sort and keep data bucketed in suitable partitions is another use case. Search Huffman codes for more detail.
Graph Searching – Traversing through a graph in graph theory operations is an ideal use case for utilizing priority queues as you can understand which nodes have been visited in a graph, and in which order.
Operations System – Investigating and understanding load balancing and interrupt handling of a system can help to determine the inputs and outputs of the system in a systematic order and approach.
Additional use cases are Number Theory, Artificial Intelligence, Statistics, Computer Networks, Spam Filtering, Discrete Optimization.
Ordered Vs. Unordered:
The main concept between ordered and unordered queues is basically the balance between complexity and speed of certain operations.
Unordered arrays – These are largely easy to inset into as order is not an issue, but on the flip side, finding the max or min object in these type of arrays can be time and resource-intensive,
Ordered Arrays – This has the exact opposite issues compared to the unordered array. If the array is already a structure, then inserting something into the right spot may be resource-heavy, but it’s always easy to find the bookends of the array.
Likely using ordered arrays is a more ideal way to build and utilize as comparing it to a library or a clean room, if things are placed where they need to go, then finding the items afterward is usually much easier.
Complete Binary Trees
To take the priority queue concept to a next level of implementation, you can start to imagine it as a Binary Tree. A binary tree is a concept of a hierarchical tree that each parent node that has only two children branches (at most) coming from it. The concept of a complete tree is that as the tree is constructed, subsequent items that are placed in the tree are ordered and built by placing the first child node to the left and the subsequent node to the right. In addition, each layer of nodes needs to be complete before a subsequent child layer can be added.
Heaps as Trees
A heap is a specific type of data structure that is at its root formed from a priority queue. As Wikipedia puts it, the heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact, priority queues are often referred to as "heaps". So as you can see the words priority queues and heaps are generally interchangeable but there are distinct differences between them. Within heaps, always the largest (or smallest) priority elements (depending on implementation) are stored as the root node and the tree is built from there. For example, if the parent nodes are always larger than the children nodes, then this is known as a Max heap and in the reverse case, they are known as Min heaps.
Fundamental Heap Operations:
There are a few fundamental heap operations that are very similar to those mentioned above in the priority queue case. The first one is removing the root of the heap and this could be done for a variety of reasons. The maintenance operations (as they are usually called) are insertion commands of sinking or swimming elements. Elements can be swum up a priority queue if they have larger values and need to be promoted a level and conversely, items are sunk if they have a lower priority as compared to other items in the same level. Lastly, items can be delMax/Min again to remove them from the tree, and then the tree is maintained to keep the completeness of it in tune.
Translating Binary Trees into an Array:
Storing trees in a programmatic means like an array allows for the computers to translate the graphical representation to one that is easier to manipulate for themselves. The table below is a basic explanation of how the array can be built from how the tree works and expanded on that same logic.
Wrap Up
In this article, we examined how both priority queues and heaps are programmatically captured conceptually and some additional use cases of how they are implemented. A good solid understanding of these core concepts can be built into developing models and simulations of real-world problems through a systematic and much more optimized approach.
As always comment, reply, and/or let me know what other topics you’d like to read about.
