Heap Operations and Priority Queues

1. What is a Binary Heap?

A binary heap is a binary tree that satisfies two fundamental properties. It's crucial to understand both, as they work in tandem to give the heap its efficiency.

1. Structural Property: It must be a Complete Binary Tree.
   A complete binary tree is a tree that is filled level by level, from left to right. There are no "gaps" in the tree. If the last level is not full, the nodes must be packed to the left. This highly regular structure is key because it allows us to represent the entire tree in a simple array, without needing pointers for parent-child relationships. For a node at index $i$, its left child is at $2i+1$, its right child is at $2i+2$, and its parent is at $\lfloor (i-1)/2\rfloor$ (for a 0-indexed array).

2. Heap Property (or Order Property):
   This property dictates the relationship between a parent and its children. There are two types of heaps based on this property:

   • Max-Heap: The value of every parent node is greater than or equal to the values of its children. This implies that the root of the tree always holds the largest element in the heap.
   • Min-Heap: The value of every parent node is less than or equal to the values of its children. Consequently, the root always holds the smallest element.

To begin, let's get a clear visual understanding of these definitions.

For the rest of this lesson, we will primarily use a max-heap for our examples. The logic for a min-heap is perfectly symmetrical—just reverse the comparisons (less than instead of greater than).

2. Core Heap Operations

The efficiency of a heap comes from its ability to maintain the heap property after an element is added or removed. These adjustments are often called "heapifying," but let's break them down into the specific operations of insertion and deletion.

Insertion: Bubbling Up

To insert a new element into a max-heap, we must preserve both the structural and heap properties. The procedure is:

1. Add the Node: To maintain the complete binary tree structure, we add the new element at the first available position in the tree, which corresponds to the end of its array representation.
2. Restore the Heap Property: The new element might violate the max-heap property (i.e., it might be larger than its parent). To fix this, we compare the new element with its parent. If it's larger, we swap them. We repeat this process—comparing and swapping the element with its new parent—moving it up the tree until it reaches a position where it is smaller than its parent, or it becomes the root. This upward movement is commonly called "bubble up" or "percolate up".

Since the height of a complete binary tree with $n$ nodes is $\lfloor {\log }_{2}n\rfloor$, this operation takes at most $O(\log n)$ time.

Deletion: Bubbling Down

In a heap, the only deletion that is typically meaningful is the deletion of the root element (the max element in a max-heap or min in a min-heap). The procedure is as follows:

1. Remove the Root: The element at the root is the one we want to extract. We can save its value to return it.
2. Replace the Root: To fill the vacant root position while maintaining the complete tree structure, we take the very last element in the heap and move it to the root.
3. Restore the Heap Property: The new root is likely much smaller than its children, violating the max-heap property. To fix this, we compare it with its children and swap it with the larger of the two. We repeat this process of comparing with children and swapping with the larger one, moving the element down the tree. This downward movement is called "bubble down," "percolate down," or sometimes simply heapify.

This operation also takes $O(\log n)$ time as the element moves from the root down to a leaf at most.

The key contrast to remember: Insertion bubbles up, Deletion bubbles down.

3. Building a Heap from an Array (The Heapify Algorithm)

A common GATE problem is to take an unsorted array of numbers and build a heap from it. You could do this by starting with an empty heap and inserting each element one by one. Since each of the $n$ insertions takes $O(\log n)$ time, this approach has a total time complexity of $O(n\log n)$.

However, there is a much more efficient, classic algorithm for this task, often called build-heap or simply heapify. It works in-place on the array and has a surprising time complexity of $O(n)$.

The algorithm is as follows:

1. Take the input array and view it as a complete binary tree (it might not satisfy the heap property yet).
2. Start from the index of the last non-leaf node. In a zero-indexed array of size $n$, this is at index $\lfloor n/2\rfloor -1$.
3. Work your way backwards from this node to the root (index 0). At each node, perform the "bubble down" procedure that we saw in the deletion operation.

The intuition is that by starting from the bottom and working up, by the time we bubble-down a node p, we can assume that the subtrees rooted at p's children are already valid heaps.

For a more detailed, step-by-step example on a larger tree, the following video is excellent.

Why is build-heap O(n)?

This is a classic analysis question and a mark of deep understanding. While a full proof is detailed, the intuition is that most of the nodes in a heap are at the bottom levels.

• The nodes at the bottom level (leaves) require 0 swaps.
• The nodes one level up require at most 1 swap.
• The nodes two levels up require at most 2 swaps.
• Only the single root node might require the full $\log n$ swaps.

When you sum the work done across all nodes, the sum converges to a value proportional to $n$, not $n\log n$. For your goal of a top GATE rank, understanding this proof is highly beneficial.

4. Application: The Priority Queue

The heap's ability to provide the min/max element in $O(1)$ time (it's always at the root) and support insertions and deletions in $O(\log n)$ time makes it the perfect data structure for implementing a Priority Queue.

A Priority Queue is an Abstract Data Type where elements have associated priorities. When you dequeue an element, you always get the one with the highest priority.

• A min-priority queue (where lower values have higher priority) is implemented with a min-heap.
• A max-priority queue (where higher values have higher priority) is implemented with a max-heap.

This is vastly superior to using an unsorted array (where finding the max is $O(n)$) or a sorted array (where insertion is $O(n)$).

Conclusion

In this lesson, we have explored the binary heap, a data structure tailored for efficient priority management. Unlike the search-oriented trees we studied before, heaps use a combination of a complete tree structure and a simple parent-child ordering rule to provide fast access to the most extreme element.

Key Takeaways:

• Heap Properties: A heap is a complete binary tree that satisfies either the max-heap or min-heap property.
• Array Representation: The complete tree structure allows for a simple and efficient pointer-less array implementation.
• Operations:
  • Insertion adds an element at the end and "bubbles up" to restore order in $O(\log n)$ time.
  • Deletion removes the root, replaces it with the last element, and "bubbles down" in $O(\log n)$ time.
• Building a Heap: The build-heap (heapify) algorithm can construct a heap from an array in-place with an optimal time complexity of $O(n)$.
• Priority Queues: Heaps are the canonical implementation for priority queues, offering efficient $O(\log n)$ insertion and extraction of the highest-priority element.

In our next lesson, we will venture into a completely different approach to data storage and retrieval: Hashing. Hashing aims to provide average-case $O(1)$ time for insertions, deletions, and searches, trading the ordered structure of trees for raw speed.