Given an array of integers nums, convert it in-place into a min-heap.
A binary min-heap is a complete binary tree where the key at the root is the minimum among all keys present in a binary min-heap and the same property is recursively true for all nodes in a Binary Tree.
To build a min-heap from the given array, the goal must be to individually heapify each non-leaf node so that it starts following the min-heap property. Once, all the non-leaf nodes are heapified, the resultant array will be a min-heap.
Heapify down is preferred in this case because the property violations occur between a node and its children when building a heap from an unsorted array. Fixing the violations downwards ensures that the entire subtree rooted at the node satisfies the min-heap property efficiently.
Note that the leaf nodes don't have any children i.e., they already follow the min-heap property. Thus, the heapifying down process is performed only for the leaf nodes.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Function to recursively heapify the array downwards
void heapifyDown(vector<int> &arr, int ind) {
int n = arr.size(); // Size of the array
// Index of largest element
int largest_Ind = ind;
// Indices of the left and right children
int leftChild_Ind = 2*ind + 1, rightChild_Ind = 2*ind + 2;
// If the left child holds larger value, update the largest index
if(leftChild_Ind < n && arr[leftChild_Ind] < arr[largest_Ind])
largest_Ind = leftChild_Ind;
// If the right child holds larger value, update the largest index
if(rightChild_Ind < n && arr[rightChild_Ind] < arr[largest_Ind])
largest_Ind = rightChild_Ind;
// If the largest element index is updated
if(largest_Ind != ind) {
// Swap the largest element with the current index
swap(arr[largest_Ind] , arr[ind]);
// Recursively heapify the lower subtree
heapifyDown(arr, largest_Ind);
}
return;
}
public:
// Function to convert given array into a min-heap
void buildMinHeap(vector<int> &nums) {
int n = nums.size();
// Iterate backwards on the non-leaf nodes
for(int i = n/2 - 1; i >= 0; i--) {
// Heapify each node downwards
heapifyDown(nums, i);
}
return;
}
};
// Driver code
int main() {
vector<int> nums = {6, 5, 2, 7, 1, 7};
// Input array
cout << "Input array: ";
for(int it : nums) cout << it << " ";
// Creating an object of the Solution class
Solution sol;
// Function call to convert the given array into a min-heap
sol.buildMinHeap(nums);
// Output array
cout << "\nMin-heap array: ";
for(int it : nums) cout << it << " ";
return 0;
}import java.util.*;
class Solution {
// Function to recursively heapify the array downwards
private void heapifyDown(int[] arr, int ind) {
int n = arr.length; // Size of the array
// Index of largest element
int largest_Ind = ind;
// Indices of the left and right children
int leftChild_Ind = 2 * ind + 1, rightChild_Ind = 2 * ind + 2;
// If the left child holds a larger value, update the largest index
if (leftChild_Ind < n && arr[leftChild_Ind] < arr[largest_Ind])
largest_Ind = leftChild_Ind;
// If the right child holds a larger value, update the largest index
if (rightChild_Ind < n && arr[rightChild_Ind] < arr[largest_Ind])
largest_Ind = rightChild_Ind;
// If the largest element index is updated
if (largest_Ind != ind) {
// Swap the largest element with the current index
int temp = arr[largest_Ind];
arr[largest_Ind] = arr[ind];
arr[ind] = temp;
// Recursively heapify the lower subtree
heapifyDown(arr, largest_Ind);
}
return;
}
// Function to convert given array into a min-heap
public void buildMinHeap(int[] nums) {
int n = nums.length;
// Iterate backwards on the non-leaf nodes
for (int i = n / 2 - 1; i >= 0; i--) {
// Heapify each node downwards
heapifyDown(nums, i);
}
return;
}
}
class Main {
// Main method
public static void main(String[] args) {
int[] nums = {6, 5, 2, 7, 1, 7};
// Input array
System.out.println("Input array: " + Arrays.toString(nums));
// Creating an object of the Solution class
Solution sol = new Solution();
// Function call to convert the given array into a min-heap
sol.buildMinHeap(nums);
// Output array
System.out.println("Min-heap array: " + Arrays.toString(nums));
}
}class Solution:
# Function to recursively heapify the array downwards
def heapifyDown(self, arr, ind):
n = len(arr) # Size of the array
# Index of largest element
largest_Ind = ind
# Indices of the left and right children
leftChild_Ind, rightChild_Ind = 2 * ind + 1, 2 * ind + 2
# If the left child holds a larger value, update the largest index
if leftChild_Ind < n and arr[leftChild_Ind] < arr[largest_Ind]:
largest_Ind = leftChild_Ind
# If the right child holds a larger value, update the largest index
if rightChild_Ind < n and arr[rightChild_Ind] < arr[largest_Ind]:
largest_Ind = rightChild_Ind
# If the largest element index is updated
if largest_Ind != ind:
# Swap the largest element with the current index
arr[largest_Ind], arr[ind] = arr[ind], arr[largest_Ind]
# Recursively heapify the lower subtree
self.heapifyDown(arr, largest_Ind)
# Function to convert given array into a min-heap
def buildMinHeap(self, nums):
n = len(nums)
# Iterate backwards on the non-leaf nodes
for i in range(n // 2 - 1, -1, -1):
# Heapify each node downwards
self.heapifyDown(nums, i)
# Driver code
if __name__ == "__main__":
nums = [6, 5, 2, 7, 1, 7]
# Input array
print("Input array:", nums)
# Creating an object of the Solution class
sol = Solution()
# Function call to convert the given array into a min-heap
sol.buildMinHeap(nums)
# Output array
print("Min-heap array:", nums)class Solution {
// Function to recursively heapify the array downwards
heapifyDown(arr, ind) {
const n = arr.length; // Size of the array
// Index of largest element
let largest_Ind = ind;
// Indices of the left and right children
const leftChild_Ind = 2 * ind + 1, rightChild_Ind = 2 * ind + 2;
// If the left child holds a larger value, update the largest index
if (leftChild_Ind < n && arr[leftChild_Ind] < arr[largest_Ind])
largest_Ind = leftChild_Ind;
// If the right child holds a larger value, update the largest index
if (rightChild_Ind < n && arr[rightChild_Ind] < arr[largest_Ind])
largest_Ind = rightChild_Ind;
// If the largest element index is updated
if (largest_Ind !== ind) {
// Swap the largest element with the current index
[arr[largest_Ind], arr[ind]] = [arr[ind], arr[largest_Ind]];
// Recursively heapify the lower subtree
this.heapifyDown(arr, largest_Ind);
}
}
// Function to convert given array into a min-heap
buildMinHeap(arr) {
const n = arr.length;
// Iterate backwards on the non-leaf nodes
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
// Heapify each node downwards
this.heapifyDown(arr, i);
}
}
}
// Driver code
const nums = [6, 5, 2, 7, 1, 7];
// Input array
console.log("Input array:", nums);
// Creating an object of the Solution class
const sol = new Solution();
// Function call to convert the given array into a min-heap
sol.buildMinHeap(nums);
// Output array
console.log("Min-heap array:", nums);
Time Complexity: O(N) (where N is the number of elements in the array)
Each heapify call has a time complexity of O(h), where h is the height of the subtree, h = log(N). The heapify operation is performed for approximately N/2 nnon-leaf nodes.
Due the variable height for all the subtrees, summing the total work done for all the nodes results in an overall time complexity of O(N) for building a heap.
Space Complexity: O(log2N)
The recursive calls during heapify require stack space proportional to the height of the heap which will be of the order of log(N) in the worst-case.
Q: Why do we start heapifying from (n//2) - 1 instead of index 0?
A: Nodes beyond (n//2) - 1 are leaf nodes, which already satisfy the heap property. We only need to heapify down from non-leaf nodes.
Q: Why is heapify down used instead of heapify up?
A: Heapify down efficiently restores the heap from the bottom up. Heapify up is useful for inserting elements one by one but is less efficient for building a heap.
Q: How does this work if the heap is stored in a linked list instead of an array?
A: Heapifying requires O(n log n) traversal time in a linked list, making it inefficient. Arrays are preferred for heaps due to direct index-based access.
Q: How would you modify this to build a max-heap instead?
A: Instead of placing the smallest child at the top, place the largest child during heapify. Change comparisons from nums[i] > nums[child] to nums[i] < nums[child].