9.1. Introduction to Heaps

So, recall that our goal is to implement a priority queue. In a priority queue, we have a sequence of jobs that keeps entering the system, each job has a priority. Whenever, we are ready to schedule a job to execute, we must pick up not the latest job or the earliest job that we got, but the job which currently has the highest priority among the waiting jobs.

In the context of computer science, a priority queue is a special type of data structure where each element has a priority associated with it. When processing tasks, instead of executing them in the order they arrive (like a regular queue), the system selects the task with the highest priority first. This behavior is crucial in scenarios where certain tasks need to be addressed more urgently than others, ensuring efficient processing of important jobs.

Think of a hospital emergency room: patients are not treated in the order they arrive; instead, those in critical condition are prioritized for treatment, similar to how a priority queue operates.

Therefore, we need an operation called delete max which will search for the highest priority job among those that are pending and schedule it next. And we obviously, have an insert operation which adds these jobs dynamically as they arrive.

To maintain an efficient priority queue, we need two important operations: 'delete max' to remove the job with the highest priority, and 'insert' to add new jobs to the queue. The challenge lies in ensuring that both operations can be executed quickly, especially when the number of jobs grows larger.

Imagine a fast-food restaurant where customers place orders. As new orders come in, the kitchen needs to quickly queue them based on urgency, such as handling large orders for events first (delete max) and adding new orders that come in (insert).

So, we saw last time that a linear structure will not allow us to simultaneously optimize these two. We end up with an order N operation for delete max or an order N operation for insert.

Using a linear structure, like an array or a simple list, results in inefficient operations. Both delete max and insert would take linear time (O(N)), meaning that as the number of jobs increases, the time taken to process these operations grows significantly, leading to inefficiency.

If you were to organize a list of tasks in a notebook and had to search through every single page to find the most important task or to add a new task, it would take a lot of time, especially as the list grows – that’s similar to how a linear structure operates.

But, we said that we will find a much better data structure using a tree of a special type called a heap. The heap is going to be a balance tree whose height is logarithmic.

A heap is a specialized tree structure that efficiently supports priority queues by maintaining two crucial properties: a specific shape (complete binary tree) and a value property (max or min values). The height of a heap tree is logarithmic in relation to the number of nodes, allowing operations like insert and delete max to be executed in logarithmic time (O(log N)), significantly speeding up the process compared to linear structures.

Consider the way books are organized in a library: a well-organized shelf allows you to quickly locate the right book without having to sift through each one sequentially, just as a heap allows efficient operations due to its structured arrangement.

So, first we start at the root, then we must add the left child of the root, then the right child and this way keep going level by level left to right. So, we add this node, then we add this node, then we add this node.

The structure of a heap ensures that nodes are filled in a specific order. Starting from the root node, each level is filled from left to right, maintaining a complete binary structure. This organized approach guarantees predictability in the shape of the tree, which is essential for efficiently implementing the heap operations.

Imagine filling a bin with balls: you start placing them from the top layer and move from left to right until the layer is full, then you move down to the next layer. This methodical approach ensures that the container is optimally filled without leaving gaps, similar to how a heap organizes its nodes.

--