Heapify Algorithm

Heaps Theory and Implementation Medium

Given an array nums representing a min-heap and two integers ind and val, set the value at index ind (0-based) to val and perform the heapify algorithm such that the resulting array follows the min-heap property.

Modify the original array in-place, no need to return anything.

Constraints

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
0 <= ind < nums.length
-10⁴ <= val <= 10⁴
nums represents a min-heap

Hints

"Compare the node with its parent at parent = (ind-1) // 2. If nums[ind] < nums[parent], swap them and move up recursively. Stop when ind == 0 (root) or no more violations exist."
"Compare the node with its left child at 2*ind + 1 and right child at 2*ind + 2. Swap with the smallest child if nums[ind] is greater. Recursively move down until heap property is restored."

Company Tags

Swiggy Robinhood Flipkart Walmart Intel Texas Instruments Western Digital Byju's Teladoc Health Freshworks Cerner NVIDIA Chewy GE Healthcare Bloomberg Target Unity Technologies Zynga Lyft Bungie KPMG Docker PwC American Express Deloitte Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/B3rrE94hf6Y/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Pre-requisite: Heaps Theory

Intuition:

When a value is updated at a particular index, the array following the min-heap property consistently gets distorted. To make the array consistent again, the heapify algorithm is used.

When a particular index value is updated, there can be two cases:

Updated value is greater than the initial value: For a min-heap array, this updated value must actually belong to its bottom subtree. Hence, the array is heapified downwards.
Updated value is smaller than the initial value: For a min-heap array, this updated value must actually belong to the upper levels of the tree. Hence, the array is heapified upwards.

While heapifying upwards or downwards, the value of the nodes are updated such that the value of parent node is always lesser than the values of its children nodes.

Approach:

The value at the specified index is updated to the given value.
If the new value is smaller than the original, the array is heapfied upwards, otherwise the array is heapified downwards.
Heapify-Up:
- Starting from the updated index, the value is compared with its parent.
- If the parent is larger, the values are swapped.
- This process continues recursively until the min-heap property is restored.
Heapify-Down:
- Starting from the updated index, the value is compared with its children.
- If either child is smaller, the smallest child is swapped with the current value.
- The process continues recursively until the min-heap property is restored.
Once the recursive call ends, the min-heap array is restored.

Solution:

#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; 
    }

    // Function to recursively heapify the array upwards
    void heapifyUp(vector<int> &arr, int ind) {
        int parent_Ind = (ind - 1)/2; 

        // If current index holds greater value than the parent
        if(ind > 0 && arr[ind] < arr[parent_Ind]) {
            // Swap the values at the two indices
            swap(arr[ind], arr[parent_Ind]);

            // Recursively heapify the upper nodes
            heapifyUp(arr, parent_Ind);
        } 

        return;
    }

public:
    // Function to implement the heapify algorithm for a min-heap
    void heapify(vector<int> &nums, int ind, int val) {

        // If the current value is replaced with a smaller value
        if(nums[ind] > val) {
            nums[ind] = val;
            heapifyUp(nums, ind);
        }

        // Else if the current value is replaced with a larger value
        else {
            nums[ind] = val;
            heapifyDown(nums, ind);
        }

        return;
    }
};

// Driver code
int main() {
    vector<int> nums = {1, 4, 5, 5, 7, 6};
    int ind = 5, val = 2;

    // Input array
    cout << "Input array: ";
    for(int it : nums) cout << it << " ";

    // Creating an object of the Solution class
    Solution sol;

    // Function call to heapify the array
    sol.heapify(nums, ind, val);

    // Output array
    cout << "\nModified array after heapifying: ";
    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 recursively heapify the array upwards
    private void heapifyUp(int[] arr, int ind) {
        int parent_Ind = (ind - 1) / 2;

        // If current index holds a greater value than the parent
        if (ind > 0 && arr[ind] < arr[parent_Ind]) {
            // Swap the values at the two indices
            int temp = arr[ind];
            arr[ind] = arr[parent_Ind];
            arr[parent_Ind] = temp;

            // Recursively heapify the upper nodes
            heapifyUp(arr, parent_Ind);
        } 

        return;
    }

    // Function to implement the heapify algorithm for a min-heap
    public void heapify(int[] nums, int ind, int val) {
        // If the current value is replaced with a smaller value
        if (nums[ind] > val) {
            nums[ind] = val;
            heapifyUp(nums, ind);
        }
        // Else if the current value is replaced with a larger value
        else {
            nums[ind] = val;
            heapifyDown(nums, ind);
        }

        return;
    }
}

class Main {
    // Main method
    public static void main(String[] args) {
        int[] nums = {1, 4, 5, 5, 7, 6};
        int ind = 5, val = 2;

        // Input array
        System.out.println("Input array: " + Arrays.toString(nums));

        // Creating an object of the Solution class
        Solution sol = new Solution();

        // Function call to heapify the array
        sol.heapify(nums, ind, val);

        // Output array
        System.out.println("Modified array after heapifying: " + 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)

        return

    # Function to recursively heapify the array upwards
    def heapifyUp(self, arr, ind):
        parent_Ind = (ind - 1) // 2

        # If current index holds a greater value than the parent
        if ind > 0 and arr[ind] < arr[parent_Ind]:
            # Swap the values at the two indices
            arr[ind], arr[parent_Ind] = arr[parent_Ind], arr[ind]

            # Recursively heapify the upper nodes
            self.heapifyUp(arr, parent_Ind)

        return

    # Function to implement the heapify algorithm for a min-heap
    def heapify(self, nums, ind, val):
        # If the current value is replaced with a smaller value
        if nums[ind] > val:
            nums[ind] = val
            self.heapifyUp(nums, ind)
        # Else if the current value is replaced with a larger value
        else:
            nums[ind] = val
            self.heapifyDown(nums, ind)

        return
    

# Driver code
if __name__ == "__main__":
    nums = [1, 4, 5, 5, 7, 6]
    ind, val = 5, 2

    # Input array
    print("Input array:", nums)

    # Creating an object of the Solution class
    sol = Solution()

    # Function call to heapify the array
    sol.heapify(nums, ind, val)

    # Output array
    print("Modified array after heapifying:", 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);
        }

        return;
    }

    // Function to recursively heapify the array upwards
    heapifyUp(arr, ind) {
        const parent_Ind = Math.floor((ind - 1) / 2);

        // If current index holds a greater value than the parent
        if (ind > 0 && arr[ind] < arr[parent_Ind]) {
            // Swap the values at the two indices
            [arr[ind], arr[parent_Ind]] = [arr[parent_Ind], arr[ind]];

            // Recursively heapify the upper nodes
            this.heapifyUp(arr, parent_Ind);
        }

        return;
    }

    // Function to implement the heapify algorithm for a min-heap
    heapify(nums, ind, val) {
        // If the current value is replaced with a smaller value
        if (nums[ind] > val) {
            nums[ind] = val;
            this.heapifyUp(nums, ind);
        }
        // Else if the current value is replaced with a larger value
        else {
            nums[ind] = val;
            this.heapifyDown(nums, ind);
        }

        return;
    }
}

// Driver code
const nums = [1, 4, 5, 5, 7, 6];
const ind = 5, val = 2;

// Input array
console.log("Input array:", nums);

// Creating an object of the Solution class
const sol = new Solution();

// Function call to heapify the array
sol.heapify(nums, ind, val);

// Output array
console.log("Modified array after heapifying:", nums);

Complexity Analysis:

Time Complexity: O(log₂N) (where N is the number of elements of the array)
The heapify function calls either heapifyUp or heapifyDown, both of which in the worst case will make number of recursive calls equal to the height of the heap which is log₂N.

Space Complexity: O(log₂N)
The recursive stack space will contribute to log₂N in the worst-case. There is no extra space used other than this as the array is modified in-place.

Code

Problem List