9.3. Examples of Heaps

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.

A priority queue is a special type of data structure where each element has a priority associated with it. Unlike a regular queue where elements are removed in the order they are added (first-in, first-out), in a priority queue, elements are removed based on their priority. This means that when it’s time to process a job, we check which job has the highest priority to execute next, regardless of the order in which jobs arrived.

Think of a hospital emergency room where patients with different levels of urgency enter (like job requests). A patient with a severe injury (high priority) will be treated sooner than those with minor ailments (low priority). The emergency room operates like a priority queue, where patients are taken care of based on the urgency of their situation.

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.

In the context of a priority queue implemented with heaps, there are two primary operations: 'insert' and 'delete max'. The 'insert' operation adds a new job along with its priority to the queue. The 'delete max' operation is then used to find and remove the job with the highest priority so that it can be executed. The efficiency of heap structures allows both these operations to be performed quickly.

Consider a ticketing system for a popular concert. When people arrive to buy tickets (insert operation), they are added to a waiting list. When it's time to admit someone to the concert (delete max operation), the person with the highest ticket tier (highest priority) is let in first.

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. But, we will find a much better data structure using a tree of a special type called a heap.

Using a simple linear structure (like an array), both 'insert' and 'delete max' operations can take linear time (O(N)), which is inefficient for managing large numbers of jobs. A heap, however, organizes data in a tree structure that allows for much quicker operations, specifically O(log N) for both inserting and removing the highest-priority job.

Imagine organizing files in a drawer. If you just throw them into the drawer in a random order, finding the file you need becomes tedious. However, if you use a labeled filing system (like a heap), you can quickly locate and remove the most important file and add new files without having to shuffle everything around.

A binary tree is a tree where we have a root and every node has 0, 1, or 2 children. However, a heap has a very specific shape where we fill up the tree nodes in a detailed order: starting at the root and adding child nodes from top to bottom, left to right.

A heap is a complete binary tree, meaning every level of the tree is fully filled except possibly for the last level, which is filled from left to right. This specific structure allows heaps to maintain their properties efficiently, like keeping the tree balanced, which helps speed up the operations.

Consider how you might pack a box with books. You would start by placing the heaviest (or largest) books on the bottom to create a stable base and then add smaller books on top. The way you stack the books resembles how nodes are organized in a heap - larger items (or higher priority) at the foundation help maintain overall stability.

The value property states that for any given node with value v1, which has children v2 and v3, v1 must be greater than or equal to v2 and v3. This is known as the max heap property.

The max heap property ensures that every parent node is greater than or equal to its child nodes. This local property aids in quickly finding the maximum value in the heap, as the highest value is always located at the root. This property must be maintained after any insertions or deletions.

Think of a family sitting around a dinner table with the oldest family member (the highest priority) positioned at the head of the table and the younger members (lower priority) on either side. The rule that the head of the table should be the oldest mirrors the relationship in a max heap, where each parent must be older (or larger) than their children.

Here is an example of the heap with 4 nodes... so this is a valid heap. There is no child of 7 at all.

The provided examples illustrate heaps that satisfy both the structural and value properties. The arrangement of nodes respects the complete tree requirement, and each parent node adheres to the max heap property, with values correctly placed to reflect this hierarchy.

Like a well-structured family tree where each generation (level) is filled before moving on to the next, ensuring the family lineage (heap structure) is clear and maintains the oldest ancestor at the top (max heap property).

Here we have something which is not a heap because the structure is wrong. You cannot leave holes and must go top to bottom left to right.

The examples of invalid heaps demonstrate how certain arrangements break the rules that make a structure a valid heap, either due to missing nodes that create 'holes' or violations of the max heap property where a parent node is smaller than its children.

Imagine stacking hay bales; if you leave gaps or misposition bales, the structure becomes unstable, just as an invalid heap becomes unusable due to its construction or adherence to priority rules.

So, let us see how it works. So, first let us insert 12. The first thing when I add a value to the heap is I must expand a tree.

When inserting a new value into a heap, the tree structure needs to grow according to the specific rules (top to bottom, left to right). After adding a new node, it may violate the max heap property, requiring adjustments such as swapping with its parent node until the property is satisfied again.

Think of adding a new player to a sports team. The new player must fit into the team hierarchy. If the new player is particularly talented (higher priority), they might need to 'swap' positions with existing team members until the best possible lineup is achieved (satisfying the heap property).

If at all the property fails, it is because the parent of the new node has a value which is too small. There is a simple way to fix this locally.

If a newly inserted node has a value greater than its parent, this indicates a violation of the max heap property. The solution is to swap the newly added node with its parent until the max heap property is reestablished. Each swap either fixes the violation or pushes the new node further up the tree where it might eventually be in the correct position.

Think of shifting promotions in a corporate hierarchy. When a new highly qualified employee joins the team, they might 'swap roles' with lower-ranked employees until the organization promotes them appropriately, maintaining the structure of authority (max heap property) within the company.

--