1. Theproblem: Handling priority
The first problem we are going to tackle is handling tasks based on priority. This is something all of us are familiar with in some way.
The problem can be described in these terms: given a collection of tasks with different priorities, determine which task should be executed next.
We can find many examples in the real world where we apply, consciously or not, techniques that help us decide what to do next. Our daily lives are full of tasks; usually the order in which we run them is a result of time constraints and the importance we assign to those tasks.
A common example of an environment where tasks are executed by priority is an emergency room, where patients are seen, not according to the order in which they arrived, but instead depending on how urgent their conditions are. If we move closer to our IT domain, there are many tools and systems that have the same behavior. Think, for instance, about your operating system scheduler. Or maybe you are using a mobile app to take a to-do list.
1.1. Priority in practice: Bug tracking
The example I’d like to use in this chapter, though, is a bug-tracking suite. You are probably already familiar with such a tool. When you work in teams, you need a way to track bugs and tasks so that no two people work on the same issue and duplicate effort, while making sure issues are tackled in the right order (whatever that is, depending on your business model).
To simplify our example, let’s restrict it to the case of a bug-tracking tool where each bug is associated with a priority, expressed as the number of days within which it needs to be solved (lower numbers mean higher priority). Also, let’s assume that bugs are independent, so no bug requires solving another bug as a prerequisite.
For our example, let’s consider the following list of bugs (in sparse order) for a single-page web application.
Each bug will look like a tuple:
<task description, importance of missing the deadline>
Whenever resources (for example, developers) are limited, there comes the need to prioritize bugs. Therefore, some bugs are more urgent than others: that’s why we associate priorities to them.
Now, suppose a developer on our team completes her current task. She asks our suite for the next bug that needs to be solved. If this list were static, our suite’s software could just sort the bugs once, and return them in order.
As you can imagine, though, this is not the case. First, new bugs are discovered all the time, and so new items will be added to the list. Say a nasty encryption bug is found— you’d need to have it solved by yesterday! Moreover, priority for bugs can change over time. For instance, your CEO might decide that you are going after the market share that’s mostly using browser X, and you have a big feature launch next Friday, the 13th, so you really need to solve that bug at the bottom within a couple of days.
2. Solutions at hand: Keeping a sorted list
We could, obviously, update our sorted list every time we have an item inserted, removed, or modified. This can work well if these operations are infrequent and the size of our list is small.
Any of these operations, in fact, would require a linear number of elements changing position, both in worst cases and in the average case.
For this use case, it could probably work. But if our list had millions or billions of elements, then we would most likely be in trouble.
2.1. From sorted lists to priority queues
Luckily for us, there is a better solution. This is the perfect use case for one of the core data structures. A priority queue will keep a partial ordering of the elements, with the guarantee that the next element returned from the queue will hold the highest priority.
By giving up the requirement of a total ordering (which we wouldn’t need in this case, because we only consume tasks one by one), we gain in performance: each of the operations on the queue can now require only logarithmic time.
As a side note, this reminds us how important it is to get our requirements right before implementing any solution. We need to make sure we don’t overcomplicate our work and requirements: for example, keeping a list of elements sorted when all we need is a partial ordering wastes resources and complicates our code, making it harder to maintain and scale.
3. Describing the data structure API: Priority queues
Before delving into the topic of the chapter, let’s take a step back.
As explained in appendix C, each data structure can be broken down into a few lower-level components:
- API—The API is the contract that a data structure (DS) makes with external clients. It includes method definitions, as well as some guarantees about the methods’ behavior that are provided in the DS’s specification. For example, a priority queue (PQ) (see table 2.1) provides these methods and guarantees:
- top() —Returns and extracts the element with the highest priority.
- peek() —Like top it returns the element with the highest priority, but without extracting it from the queue.
- insert(e, p)—Adds a new element e with priority p to the PQ.
- remove(e) —Removes element e from the queue.
- update(e, p)—Changes the priority for element e and sets it to p.
- Invariants—(Optional) internal properties that always hold true throughout the life of the data structure. For instance, a sorted list would have one invariant: every element is not greater than its successor. The purpose of invariants is making sure the conditions necessary to live up to the contract with the external clients are always met. They are the internal counterparts of the guarantees in the API.
- Data model—To host the data. This can be a raw chunk of memory, a list, a tree, etc.
- Algorithms—The internal logic that is used to update the data structure while making sure that the invariants are not violated.
In appendix C we also clarify how there is a difference between an abstract data structure and concrete data structures. The former includes the API and invariants, describing at a high level how clients will interact with it and the results and performance of operations. The latter builds on the principles and API expressed by the abstract description, adding a concrete implementation for its structure and algorithms (data model and algorithms).
This is exactly the relationship between priority queues and heaps. A priority queue is an abstract data structure that can be implemented in many ways (including as a sorted list). A heap is a concrete implementation of the priority queue using an array to hold elements and specific algorithms to enforce invariants.
3.1. Priority queue at work
Imagine you are provided with a priority queue. It can come from a third-party library or from a standard library (many languages, such as C++ or Scala, provide an implementation for priority queues in their standard container lib).
You don’t need to know the internals of the library at this point; you just need to follow its public API and use it, confident it’s properly implemented. This is the black box approach (figure 2.1).
For instance, let’s suppose we add our bugs to our PQ in the same order we have seen before.
If we returned the tasks in the same order as we inserted them, we would just implement as a plain queue (see figure 2.2 for a quick glance at how a queue works, and appendix C for a description of basic containers). Instead, let’s assume that now we have our priority queue containing those five elements; we still don’t know the internals of the PQ, but we can query it through its API.
Figure 2.1 Representation of a priority queue as a black box. If we employ an implementation of a priority queue provided by a third-party library (or from standard libraries), and we trust this implementation to be correct, we can use it as a black box. In other words, we can ignore its internals, and just interact with it through its API.
For instance, we can check how many elements it contains and even take a peek at the one at the top (figure 2.1). Or we can directly ask it to return us the top element (the one with the highest priority) and remove it from the queue.
If, after inserting the five elements in figure 2.1, we call top, the element returned will be “UI breaks on browser X” and the size of the queue will become 4. If we call top again, the next element will be “CSS style causes misalignment” and the size will become 3.
As long as the priority queue is implemented correctly and given the priorities in our examples, we can be sure those two elements will be the ones returned first, independently of the order in which they are inserted.
Figure 2.2 Operations on a queue: elements are generic integers, but they could be any value here, because in plain queues priority is only given by the order of insertion (see appendix D). Insertion (enqueue) adds an element to the front of the queue. Deletion (dequeue) removes the last element in the queue and returns it. With some caution, both operations can be performed in constant time.
3.2. Priority matters: Generalize FIFO
Now the question is how we choose the priority of an element. Often, the natural ordering given by how much time an element waits in a line can be considered the fairest. Sometimes, however, there is something special about some elements that might suggest they should be served sooner than others that waited longer. For instance, you don’t always read your emails in the order you received them, but often you skip newsletters or “funny” jokes from friends to read work-related messages first. Likewise, in an emergency room, the next case treated is not necessarily going to be one that has been waiting for the longest time. Rather, every case is evaluated at arrival and assigned a priority, and the highest priority one is going to be called in when a doctor becomes available.
That’s the idea behind priority queues: they behave like regular, plain queues, except that the front of the queue is dynamically determined based on some kind of priority. The differences caused to the implementation by the introduction of priority are profound, enough to deserve a special kind of data structure.
But that’s not all: we can even define basic containers as bag or stack as special cases of priority queues; appendix D explores how this is possible. This is an interesting topic to help you gain a deeper understanding of how priority queues work, although in practice those containers are usually implemented ad hoc, because we can achieve better performance by leveraging their specific characteristics.
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)