9.2.2. Heap Shape and Value Property

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. 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.

A priority queue is a data structure that allows us to manage a collection of jobs based on their importance or priority. The main operations involved are 'delete max', which removes the highest priority job from the queue, and 'insert', which adds new jobs to the queue. This means we are not just processing jobs in the order they arrive, but rather focusing on processing the most important ones first, ensuring efficiency in handling tasks.

Imagine a hospital emergency room where patients are prioritized based on the severity of their conditions rather than their arrival time. The triage nurse uses a priority queue to manage patient care, ensuring that the most critical patients are seen first, even if they arrived later than less critical cases.

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. Then, we saw trivial two dimensional array which gives us an N root N solution that is the root N operation for each of these, so our N operations is order N to N. But, we said that we will find a much better data structure using a tree of a special type called a heap.

In traditional linear data structures, managing both insertions and deletions efficiently can be challenging, often leading to one operation being slower than the other. However, heaps provide a solution. They have a logarithmic height relative to the number of nodes, allowing both insertion ('insert') and removal ('delete max') to be performed in logarithmic time, making the operations much faster and efficient compared to linear structures.

Consider a ticketing system for a concert where you can either buy tickets (insert operation) or let go of your reserved tickets (delete max operation). An efficient system ensures that you can find the best available seats quickly, regardless of how many tickets have been sold similarly to how heaps optimize operations.

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, binary trees in general can have arbitrary shapes. So, we could have binary trees which look like this, where the root has 1 child, this has 2 children or it could look even more skewed in one direction. So, binary trees can have very strange shapes, but a heap is a binary tree which has a very specific shape, where we fill up the tree nodes or we add the tree nodes in a specific order.

A heap is a type of binary tree with a strict shape property. It must be filled from top to bottom, left to right, without any gaps between nodes. This means if you have a tree with n nodes, the shape will be consistently defined, allowing for efficient management of the nodes and adherence to the heap properties.

Think about organizing a library shelf where books are arranged from top to bottom and left to right without leaving empty spaces. This systematic organization (like the strict shape of a heap) allows for quicker access and better management of the collection.

So, the value property says that... So, what does happening in the tree is that we have nodes and each nodes is the value, so whenever I see a node with value v 1 which has children v 2 and v 3, then what we want is, this is bigger than or equal to v 2 and bigger than or equal to v 3. So, among these three nodes the largest one must be v 1, so this is what is called the max heap property.

In a max heap, the value property requires that each parent node must have a value greater than or equal to its children. This local rule maintains the overall property of the heap, ensuring that the highest value remains at the root of the heap, facilitating the 'delete max' operation.

Imagine a hierarchical company structure where the CEO (top node) has more authority than the managers (children nodes) beneath him. This structure ensures decisions made at higher levels take precedence—similarly, the values in a max heap must respect parent-child authority in the same way.

So, here is an example of the heap with 4 nodes,... So, every leaf node which has no children always satisfies the heap property. So, once you have a leaf node, then nothing to check.

When examining heaps, if a structure does not meet the shape or value property, it is not a valid heap. A valid heap is defined by its shape (filled from top to bottom and left to right) and value property (parents must be greater than children). Leaf nodes automatically satisfy the heap property since they have no children to compare to.

Think of a pyramid made of blocks where each block must support those above it. If a block (parent node) is weaker (lower value) than those it supports (child nodes), the structure is compromised, making it invalid, much like how any violation of heap properties renders it unusable.

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,... So, if at all the property fails, it is because the parent of the new node has a value which is too small. So, there is a simple way of fix this locally at least and that is to exchange these two.

When inserting into a heap, a new value is added as a leaf node, which may disrupt the heap property if it's greater than its parent node. The process to fix this involves swapping the new value with its parent until the heap property is restored. This process continues until the inserted value is in the correct position, ensuring the hierarchy remains intact.

Consider entering a new player into a sports team ranking; if the new player (inserted value) is better than the current top player (parent), they swap rankings until the best player remains at the top. This direct swapping maintains order without affecting the relationships of other players in between.

--