9.4.2. Maintaining Heap Properties

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 a priority queue, jobs are managed based on their priority rather than the order in which they arrive. This means that when you're ready to execute a job, you can't just pick the first one that came in; you have to look for the job with the highest priority among all the jobs in the queue. This is crucial for efficiently managing tasks in systems where some tasks are more urgent than others.

Imagine you are at a busy hospital emergency room. Patients do not get treated in the order they arrive; instead, the ones with the most critical conditions are prioritized. This ensures that resources are allocated effectively to save lives based on immediate need rather than arrival time.

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. ... Therefore, processing N jobs will take time N log N as supposed to N root N for the array or N square for the linear representation.

In simpler data structures like linear lists or arrays, performing operations like deletion or insertion can become inefficient, often O(N). However, heaps provide a better alternative where both insertion and deletion operations can be performed at O(log N) time due to their balanced tree structure. This efficiency substantially reduces the total processing time when managing multiple jobs.

Consider organizing a race. If you use a linear queue, runners start based on who arrives first, which can be chaotic and slow to manage. If you switch to a prioritized system where the fastest runners leave first, the overall time spent until all runners finish would be much shorter, just like a heap making job handling efficient.

So, let us start looking first at what a heap test. So, a binary tree is a tree where we have a root and every node has 0, 1 or 2 children.... So, that is the first feature of the heap that if I have a heap with n nodes, then the shape of the tree is deterministically fixed by this rule that the n nodes must be inserted top to bottom, left to right.

Heaps are a specific type of binary tree characterized by their structure which is organized from top to bottom and left to right without any gaps. This makes it easy to infer the shape of the heap based on the number of nodes it contains. The ability to predict the tree structure with certainty is a crucial aspect that differentiates heaps from arbitrary binary trees.

Think of arranging books on a shelf where you must fill each row before starting the next one. If you put a book out of order or leave gaps, it becomes messy. A heap maintains order like a neatly arranged shelf, ensuring that every space is thoughtfully filled.

So, the value property says that... So, what does happen in the tree is that we have nodes and each nodes is the value, so whenever I see a node with value v1 which has children v2 and v3, then what we want is, this is bigger than or equal to v2 and bigger than or equal to v3.

In a max heap, each parent node must be larger than or equal to its children. This relationship ensures that the highest priority job can always be found at the root of the tree, allowing for efficient retrieval. Thus, whenever you need to access the job with the highest priority, you can always look at the root.

Consider a family where the parents have the most authority or responsibility, and the children follow their lead. The parents represent the higher values in the max heap, which is always on top, ensuring that decisions are prioritized correctly.

So, here is an example of the heap with 4 nodes... So, these are two examples of heaps. ... So, this node 8 actually violates the heap property, so something can fail to be a heap, either because the tree structure is wrong or because at some node the heap property is violated.

A valid heap must adhere to both the structural properties and the max heap property. If a node violates the heap property by being smaller than its children, or if the structure does not fill properly, the tree can no longer function as a heap. Recognizing valid and invalid heaps is necessary for the maintenance of these data structures.

Think of a sports tournament where teams are placed in multiple levels based on performance. If a lower-performing team (child) is in a higher position (parent), it disrupts the hierarchy, creating confusion about team rankings, just like a violated heap where priorities are mixed up.

So, now we have to implement these two operations on heaps, insert and delete max. So, let us see how it works? So, first let us insert 12... but now I change the value at this point. So, I have to look at this configuration to see whether what I move the 12 into violates heap property or not.

When inserting a new value into a heap, it is initially added at the lowest level (as a leaf). After insertion, the max heap property might be violated, so the newly added node needs to be compared with its parent and, if necessary, swapped until the heap property is restored. This process is called 'percolating up.'

Imagine adding a new employee to a team based on ranking. If the new employee is more experienced (higher priority) than their supervisor, they would need to swap roles to maintain the correct hierarchy in the company. The heap adjusts in a similar way to keep the highest priority at the top.

--