Convert Min Heap to Max Heap
Introduction
The need to convert min heap to max heap arises in scenarios where a change in the ordering of elements is required. This process involves a systematic rearrangement of the elements within the heap to adhere to the max heap property.
The terms “min heap” and “max heap” refer to binary trees with distinct ordering properties. A min heap is characterized by nodes having values less than or equal to their children, while a max heap dictates that each node must have a value greater than or equal to its children.
What is Min Heap and Max Heap?
Converting a min heap to a max heap involves rearranging the elements of the heap to satisfy the max heap property. Before diving deep into the conversion,
- let us understand the concept of Min heap and Max heap.
Min Heap
A Min Heap is a binary tree where the value of each parent node is less than or equal to its children.
- The smallest element is at the root.
- Used when the highest priority is the smallest value.
Max Heap
A Max Heap is a binary tree where the value of each parent node is greater than or equal to its children.
- The largest element is at the root.
- Used when the highest priority is the largest value.
Key Differences of Min Heap and Max Heap :
| Feature | Min Heap | Max Heap |
|---|---|---|
| Root Node | Smallest element | Largest element |
| Priority | Lowest value = top | Highest value = top |
| Usage | Dijkstra, A* Algorithm | Heap Sort, Top-K problems |
| Property | Parent ≤ children | Parent ≥ children |
Example for conversion of min heap to max heap
Consider the following min heap:
5
/ \
9 11
/ \ / \
14 13 12 20
Applying the conversion algorithm:
- Start from the last non-leaf node (9 at index 1).
- Traverse in reverse order: 11, 5.
- Perform max heapify at each node.
After conversion:
20
/ \
14 13
/ \ / \
9 11 12 5
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Conversion Algorithm
To convert a min heap to a max heap, you can follow these steps:
- Start from the last non-leaf node: Begin the conversion process from the last non-leaf node in the heap. The last non-leaf node can be found at index (n/2) – 1, where ‘n’ is the number of elements in the heap.
- Traverse in reverse order: Traverse the heap in reverse order (from the last non-leaf node to the root).
- Heapify each node: For each node encountered during the traversal, perform a “max heapify” operation to ensure the max heap property is satisfied.
- Max Heapify Operation: Compare the node with its children, and swap the node with the larger child if necessary. Continue this process recursively until the max heap property is satisfied for the subtree rooted at the current node.
Implementation for Convert Min Heap to Max Heap
Here’s a Python implementation of the conversion:
def max_heapify(arr, n, i):
largest = i
left_child = 2 * i + 1
right_child = 2 * i + 2
if left_child < n and arr[left_child] > arr[largest]:
largest = left_child
if right_child < n and arr[right_child] > arr[largest]:
largest = right_child
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
max_heapify(arr, n, largest)
def convert_min_heap_to_max_heap(arr):
n = len(arr)
# Start from the last non-leaf node and apply max-heapify
for i in range((n // 2) - 1, -1, -1):
max_heapify(arr, n, i)
# Example usage
min_heap = [5, 9, 11, 14, 13, 12, 20]
print("Min Heap before conversion:", min_heap)
convert_min_heap_to_max_heap(min_heap)
print("Max Heap after conversion:", min_heap)
Output :
min_heap = [5, 9, 11, 14, 13, 12, 20]
After applying conversion, the output will be:
Max Heap after conversion: [20, 14, 12, 9, 13, 11, 5]
Explanation :
- The objective is to convert a Min Heap into a Max Heap.
- The original min_heapify() function maintains the Min Heap property, which is incorrect for this task.
- To convert properly, use a max_heapify() function and apply it from the last non-leaf node up to the root.
- Example: Min Heap [5, 9, 11, 14, 13, 12, 20] becomes Max Heap [20, 14, 12, 9, 13, 11, 5] after conversion.
- The resulting Max Heap satisfies the property where each parent node is greater than or equal to its children.
Time & Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Build Max Heap from Min Heap | O(n) | O(1) |
| Single max_heapify() Call | O(log n) | O(log n) |
| Complete Conversion Process | O(n) | O(1) |
Practical Applications
Python Code Using heapq (Standard Heap Library)
Python’s heapq only supports Min Heaps by default.
To simulate a Max Heap, we can:
- Negate all elements, use heapq, then negate again to get actual values.
import heapq
def min_to_max_heap_with_heapq(min_heap):
# Negate all values
max_heap = [-x for x in min_heap]
# Apply heapify (now acts like max heap using negated values)
heapq.heapify(max_heap)
# Convert back to positive values
return [-x for x in max_heap]
# Input Min Heap
min_heap = [1, 3, 5, 7, 9, 11]
# Convert using heapq
max_heap = min_to_max_heap_with_heapq(min_heap)
print("Max Heap (via heapq):", max_heap)
Note: heapq does not guarantee full tree-based Max Heap structure, but it maintains the heap property at the array level.
Explanation:
- Python’s heapq supports only Min Heaps by default.
- To simulate a Max Heap, all elements are negated.
- heapq.heapify() is applied on the negated list.
- After heapify, elements are negated again to get original values in Max Heap form.
- The final list satisfies the Max Heap property with the largest element at the root.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Negating all elements | O(n) | O(n) |
| heapq.heapify() | O(n) | O(1) |
| Negating again (final conversion) | O(n) | O(n) |
| Total Conversion Process | O(n) | O(n) |
To wrap it up:
Converting a min heap to a max heap is a valuable skill in manipulating heap structures efficiently. This process is applicable in scenarios where a change in ordering is necessary, offering flexibility in various applications such as priority queues and sorting algorithms.
By understanding the conversion algorithm and its principles, you gain a deeper insight into the dynamics of heap data structures.
FAQs
You can convert a Min Heap to a Max Heap by building a Max Heap using the same elements, starting from the last non-leaf node using heapify. This approach works in O(n) time.
Yes, Python’s heapq supports only Min Heap, so we simulate a Max Heap by inserting negative values and then negating them back when retrieving.
Using the heapify method from the bottom-up approach, the time complexity is O(n), which is faster than inserting each element individually (O(n log n)).
Conversion is useful when algorithms require the maximum element first, such as in scheduling or priority queues where priorities must be reversed.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment