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 data structure where each node’s value is less than or equal to the values of its children. This ordering property ensures that the minimum value is at the root, making it efficient for tasks like extracting the minimum element.
Max Heap
A max heap dictates that each node’s value must be greater than or equal to the values of its children. The maximum value resides at the root, facilitating quick access to the maximum element.
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
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 min_heapify(arr, n, i):
smallest = i
left_child = 2 * i + 1
right_child = 2 * i + 2
if left_child < n and arr[left_child] < arr[smallest]:
smallest = left_child
if right_child < n and arr[right_child] < arr[smallest]:
smallest = right_child
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
min_heapify(arr, n, smallest)
def convert_min_heap_to_max_heap(arr):
n = len(arr)
# Start from the last non-leaf node and perform min heapify
for i in range((n // 2) - 1, -1, -1):
min_heapify(arr, n, i)
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 Python code converts a min heap to a max heap. The “min_heapify” function maintains the min heap property, and the “convert_min_heap_to_max_heap” function iterates from the last non-leaf node, applying min_heapify. The example converts the min heap [5, 9, 11, 14, 13, 12, 20] to the max heap [20, 14, 12, 9, 13, 11, 5]. This process ensures that the max heap property—each node having a value greater than or equal to its children—is satisfied, facilitating efficient data manipulation in various applications.
Practical Applications
Complexity analysis of Convert Min heap to Max heap
Time Complexity: O(n)
The time complexity for converting a min heap to a max heap is O(n), where n is the number of elements in the heap.
Auxiliary Space: O(log n)
The space complexity for converting a min heap to a max heap is O(log n), where n is the number of elements in the heap because the stack follows the recursion technique.
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.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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