9. Heaps

Let us now look at Heaps. Module – 05 Lecture - 35 (Refer Slide Time: 00:03) 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. 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.

In this chunk, we introduce the concept of heaps, focusing on their role in implementing a priority queue. A priority queue is a data structure where each element has a priority, and elements are served based on their priority rather than their arrival time. This requires operations like 'delete max' to remove the highest priority element and 'insert' to add new elements. The key takeaway is understanding the importance of managing priorities in scheduling jobs effectively.

Think of a restaurant where customers are seated based on the reservation priority rather than just their arrival time. For instance, if a VIP guest arrives, they are seated immediately, even if other customers have been waiting longer. Similarly, in a priority queue, the 'delete max' operation ensures that the highest-priority job is processed next.

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.

This chunk discusses why linear structures (like arrays) are not efficient for implementing priority queues. In a linear structure, operations such as 'delete max' or 'insert' have a time complexity of O(N), meaning they take linear time relative to the number of elements. A better solution is proposed using heaps, which can optimize both operations. This sets the stage for explaining heaps as more efficient data structures.

Consider a library where book requests are handled in the order they arrive (linear structure). If a highly requested book comes in, it may be lost in the queue (like in a linear structure). However, if the library used a priority system (a heap), the most requested books would always be retrieved first, improving efficiency.

So, the heap is going to be a balance tree whose height is logarithmic in the size that is if flag N nodes in the tree, the height that is the number of edges from the root to any leaf will be log N. And with this, it will turn out the both insert and delete max are prepositional to log N and 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. We also said that this heap in principle is flexible and can grow as large as we want.

In this chunk, we describe the structure of heaps as a balanced binary tree with a height of O(log N), where N is the number of nodes. This logarithmic height ensures that both 'insert' and 'delete max' operations can be performed in logarithmic time, resulting in a total complexity of O(N log N) for processing N jobs. Additionally, heaps can dynamically adjust their size, making them efficient and scalable.

Imagine a multi-story parking garage where each level can hold a set number of cars (nodes). With a balanced design, finding a parking spot (inserting a car) or retrieving a car (deleting the highest priority) can be done quickly, since you’d never have to search through all the floors. This is similar to how heaps work with efficient access to their 'positions'.

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.

This chunk introduces the specific structure of heaps. While a binary tree can have various shapes, heaps must conform to a strict shape, where nodes are filled from the top down and left to right. This deterministic structure simplifies operations on heaps, as you can predict the tree's layout based on the number of nodes.

Consider arranging seats in a theatre. The first row must be filled entirely before moving to the next row, and seats are filled from left to right. This structure ensures all available space is utilized and allows for easy navigation, akin to how heaps are structured.

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. So, this is the local property, it just tells us at every node look at that node, look at the 2 children, the node must be bigger than it is 2 children.

This chunk explains the max heap property, which states that each parent node must be greater than or equal to its children. This ensures that the largest element is always at the root of the heap, making the 'delete max' operation straightforward. Essentially, it enforces a specific ordering among the values in the heap structure.

Think of a sports tournament where only the top team (the max) can advance to the finals. Similarly, in a heap, the parent node (top team) must be stronger than its child nodes (other teams), ensuring the highest priority is preserved at the root.

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 insert 12 means I have to add a value to the heap. So, the first thing when I add a value to the heap is I must expand a tree. So, where do I put this node? So, this now fixed because we know that heaps can only grow and shrink in a particular way, so I must add the new node left to right, top to bottom.

Here, we delve into the operational mechanics of heaps. The insert operation involves adding a new value in the appropriate position as dictated by the heap structure (left to right, top to bottom) and then ensuring that the max heap property is maintained. This may require swapping the inserted value with parent nodes until the property is satisfied. Understanding this process is crucial for implementing heaps effectively.

Imagine planting a tree where you add branches (new elements) in a specific manner so that it grows uniformly. If a new branch (value) is taller than its parent branch, you’d swap their positions to maintain the hierarchy. This is similar to how we manage the heap after inserting a new value.

--