What is Heap?
A Heap is a special type of binary tree that satisfies the following two properties:
a. Structural Property: It must be a Complete Binary Tree (CBT), in which all levels are completely filled except possibly the last level, which is filled from left to right.
b. Ordering Property: It must satisfy either the Max Heap property or the Min Heap property.
- Max Heap: Every parent node must be greater than or equal to its children.
- Min Heap: Every parent node must be less than or equal to its children.
Before exploring heap operations, let us first understand the concept of a Complete Binary Tree, as it forms the structural foundation of a heap.
A Complete Binary Tree is a binary tree in which all levels are completely filled except possibly the last level. The last level is filled from left to right, without leaving any gaps between nodes.
For example:
A complete binary tree
Note: A complete binary tree alone is not necessarily a heap. It must satisfy both the structural property and the ordering property.
Types of Heap Trees
a. Max Heap
In a max heap, every parent node is greater than or equal to its children. Therefore, the largest element is always at the root.
Example:
Max heap
Here, 50 is the largest element and is placed at the root.
b. Min Heap
In a min heap, every parent node is less than or equal to its children. Therefore, the smallest element is always at the root.
Example:
Min heap
Here, 5 is the smallest element and is placed at the root.
Important Properties of a Heap
- A heap is a complete binary tree.
- A max heap stores the largest element at the root.
- A min heap stores the smallest element at the root.
- A heap is commonly implemented using an array.
- A heap is not necessarily a Binary Search Tree (BST).
Array Representation of a Max Heap
A heap can be represented efficiently using an array for the parent-child relationships.
Example: A = {50, 45, 40, 20, 25, 35, 30, 10, 15}
Array representation:
For a heap stored using a zero-based array, these formulas help us navigate the heap:
- Parent of index i:
(i - 1) / 2 - Left child of index i:
2 * i + 1 - Right child of index i:
2 * i + 2
Integer division is used for the parent formula.
Example 1: Find the children of 45
- Index of 45 = 1
- Left child index = 2 * 1 + 1 = 3 → value 20
- Right child index = 2 * 1 + 2 = 4 → value 25
Example 2: Find the parent of 35
- Index of 35 = 5
- Parent index = (5 – 1) / 2 = 2 → value 40
Example 3: Find the children of 20
- Index of 20 = 3
- Left child index = 2 * 3 + 1 = 7 → value 10
- Right child index = 2 * 3 + 2 = 8 → value 15
Important note: The parent formula applies only to non-root nodes. The root at index 0 has no parent.
Insertion in a Max Heap
When a new element is inserted, it is first placed at the next available position to preserve the complete binary tree structure.
Then, it is compared with its parent. If the new element is greater than its parent, the two elements are swapped. This process continues until the heap property is restored.
This process is called heapify up or sift up.
Example: Insert 60 into the following max heap.
Before inserting 60:
Step 1: Add 60 at the next available position.
Step 2: Compare 60 with its parent node i.e. 25. It is violating the property of max heap, swap them.
Step 3: Again compare 60 with its parent node i.e. 45, child is greater than parent, swap them.
Step 4: Again compare 60 with its parent node i.e. 50, child is greater than parent, swap them.
Final Max Heap after insertion
Deletion in a Max Heap
When an element is deleted from a max heap, the root element (the maximum element) is usually removed first.
The last element in the heap is moved to the root position to maintain the complete binary tree structure. Then, it is compared with its children. If the element is smaller than its larger child, the two elements are swapped. This process continues until the heap property is restored.
This process is called heapify down or sift down.
Note: In a max heap, the delete-max operation removes the root element, which contains the maximum value. In a min heap, the delete-min operation removes the root element, which contains the minimum value.
Steps to delete an element from max heap
Step 1: Remove the root element i.e. 50.
Step 2: Move the last element to the root, and reduce the size of heap by 1.
Step 3: Compare 15 with its children (45 and 40). Since 15 is smaller than its larger child i.e. 45, swap 15 and 45.
Step 4: Compare 15 with its children (20 and 25). The larger child is 25. Swap 15 and 25. Now 15 has no children, so the heap property is restored.
Final Max Heap after deletion
Time Complexity of Heap Operations
| Operation | Time Complexity |
|---|
| Access maximum in a max heap | O(1) |
| Insert an element | O(log n) |
| Delete the root | O(log n) |
| Build a heap | O(n) |
| Heap sort | O(n log n) |
| Search for an element | O(n) |
Heap Sort
Heap Sort is a comparison-based sorting algorithm that uses a heap data structure to arrange elements in ascending or descending order.
To sort elements in ascending order, Max Heap is used, and to sort elements in descending order, Min Heap is used.
Steps involved in Heap Sort
- Build a Max Heap: Convert the given array into a max heap so that the largest element is at the root.
- Swap the root with the last element: The largest element moves to its correct position at the end of the array.
- Reduce the heap size: Exclude the last element from the heap because it is already sorted.
- Heapify down: Restore the max heap property by moving the root element down to its correct position.
- Repeat: Continue swapping the root with the last element in the remaining heap, reducing the heap size and heapifying until only one element remains.
Applications of Heap Trees
Heap trees are used in many computer science applications:
- Priority Queues: Process high-priority tasks first.
- Heap Sort: Sort elements efficiently.
- Operating Systems: Support priority-based scheduling.
- Graph Algorithms: Help implement Prim’s and Dijkstra’s algorithms using priority queues.
- Event Simulation: Process events according to their scheduled times or priorities.
Heap Tree vs Binary Search Tree
| Feature | Heap Tree | Binary Search Tree |
|---|
| Structure | Complete binary tree | Not necessarily complete |
| Ordering | Parent-child heap property | Left subtree values are smaller and right subtree values are larger, under the usual distinct-key rule |
| Root | Maximum in max heap; minimum in min heap | No guaranteed minimum or maximum at root |
| Searching | Usually O(n) | Average O(log n) if reasonably balanced; worst case O(n) |
| Main applications | Priority queues and heap sort | Searching, insertion, and deletion |
Conclusion
The Heap Data Structure is an important non-linear data structure that helps efficiently manage and retrieve the maximum or minimum element. By satisfying the structural property of a Complete Binary Tree and the ordering property of a Max Heap or Min Heap, it supports efficient operations such as insertion and deletion.
Understanding heap constructions, array representation, heapify operations, and Heap Sort provides a strong foundation for learning advanced data structures and algorithms. Heaps are widely used in priority queues, scheduling systems, and graph algorithms, making them an essential concept in computer science.
