9.2. Heap Structure and 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.

A priority queue is a fundamental data structure where elements are processed based on their priority rather than their order in the queue. This means that even if a job arrives later, it could still be prioritized over an earlier job if it has a higher priority. Thus, the heap data structure is important for efficiently implementing this capability in computer algorithms.

Imagine you're at a busy restaurant where customers are seated based on their reservation priority rather than their arrival order. If a VIP guest arrives, they get seated immediately, no matter how many customers are already waiting. This is similar to how a priority queue operates.

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.

The two main operations required in a priority queue are: 'insert', which adds a job with a priority, and 'delete max', which removes the job with the highest priority. In a conventional queue, items are removed in the order they arrive; however, in a priority queue, how jobs are handled can significantly differ based on their priority levels.

Think of an ambulance on the road. Despite being in a traffic jam, it has the highest priority to get through. It can maneuver and push other cars aside (similar to executing a delete max operation) while new cars (insert operations) keep coming into the traffic. The ambulance's priority ensures it gets through first.

We saw 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 data structure (like an array or a linked list) to implement a priority queue leads to inefficiencies. Both the insert and delete max operations could take linear time, which is inefficient as it doesn't scale well with an increase in the number of jobs.

It's similar to a traditional library where books are arranged one after another. If you need to fetch the most popular book (similar to delete max), you'd have to search through every single book, which can take a long time, especially since new books keep arriving.

The heap is going to be a balanced tree whose height is logarithmic in the size that is if I have N nodes in the tree, the height will be log N.

Heaps are structured as complete binary trees, where all levels of the tree are fully filled except possibly for the last level, which is filled from left to right. This structure allows both insert and delete max operations to be performed in logarithmic time, greatly enhancing performance compared to linear structures.

Envision a perfectly balanced pyramid where every row is filled completely before moving to the next. If you had to add a level, you would start from the left corner and gradually fill it till completion. This systematic filling allows you quick access (fast operations).

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

Heaps possess two key properties: the shape property and the value property. The shape property insists on the complete binary tree structure, while the value property (for max heaps) requires each parent node to be greater than or equal to its child nodes. This ensures that the maximum element is always at the root, allowing quick access.

Think of a family tree where a parent (representing a node with a higher value) must have children (nodes with lower values). If every child were taller than the parent, the tree wouldn't make sense (analogous to breaking the value property).

Here is an example of the heap with 4 nodes, so first because it is 4 nodes, every 4 node heap will have the shape. Because, the first node will be the root, the second will be the roots left child, third node will be the right child and the fourth node will start a new line, then moreover we can check the heap property.

In this example, the shape of a valid heap with four nodes follows the stipulated rules: each node correctly positioned according to the complete binary tree structure, and the values assigned to each node uphold the heap property. This showcases how heaps are built and verified for validity.

Picture building a tower of blocks. You start with a broad base (the root), then stack blocks level by level. If you try to put a block on top of another that isn't stable, the structure collapses. The rules on block stacking mimic heap properties.

So, here we have something which is not a heap because the structure is wrong. So, we said that you cannot leave holes, you must go top to bottom left to right, so there should be some node here, before you add the node in the right.

Invalid heaps can occur due to structural issues or violations of the heap property. For instance, leaving gaps (holes) in the binary tree structure violates the shape property. Additionally, if a parent node is smaller than one of its child nodes, the value property is violated.

Imagine a seating arrangement in a theater. If there’s an empty seat in a row (a hole), it disrupts the pattern and can confuse attendees (similar to how a structural problem affects a heap). Also, if a smaller person (node) is sitting in front of a taller person (child), it visually breaks the expected order.

--