Problem Statement

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.

Examples

Example 1:

Input: nums = [1, 4, 5, 5, 7, 6], ind = 5, val = 2
Output: [1, 4, 2, 5, 7, 5]

Explanation: After setting index 5 to 2, the resulting heap in array form = [1, 4, 5, 5, 7, 2]
Parent of nums[5] = nums[2] = 5 > nums[5] = 2, so they are swapped.
Final array = [1, 4, 2, 5, 7, 5]

Input: nums = [2, 4, 3, 6, 5, 7, 8, 7], ind = 0, val = 7
Output: [3, 4, 7, 6, 5, 7, 8, 7]

Explanation: After setting index 0 to 7, the resulting heap in array form =[7, 4, 3, 6, 5, 7, 8, 7]
The parent of nums[2] = nums[0] = 7 > nums[2] = 3, so they are swapped. No further swaps are needed.
Final array = [3, 4, 7, 6, 5, 7, 8, 7]

Different Approaches

1️⃣ Heap

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:

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

Code:

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    // Function to adjust the heap downward (min-heap) from the given index.
    // It ensures the element at index 'ind' moves to the correct position to maintain the heap property.
    void heapify_down(vector<int>& nums, int ind) {
        int n = nums.size();
        int smallest = ind;  // Assume current index is the smallest
        
        // Calculate the left and right child indices.
        int left = 2 * ind + 1;
        int right = 2 * ind + 2;

        // Check if the left child exists and is smaller than the current element.
        if (left < n && nums[left] < nums[smallest]) {
            smallest = left;
        }
        // Check if the right child exists and is smaller than the current smallest.
        if (right < n && nums[right] < nums[smallest]) {
            smallest = right;
        }
        // If a smaller child is found, swap and continue heapifying down.
        if (smallest != ind) {
            swap(nums[smallest], nums[ind]);
            heapify_down(nums, smallest);
        }
    }

    // Function to adjust the heap upward (min-heap) from the given index.
    // It ensures the element at index 'ind' moves up to the correct position to maintain the heap property.
    void heapify_up(vector<int>& nums, int ind) {
        // Base case: if the current element is the root, no parent exists.
        if (ind <= 0) return;

        // Calculate the parent's index.
        int parent = (ind - 1) / 2;

        // If the parent is greater than the current element, swap them.
        if (nums[parent] > nums[ind]) {
            swap(nums[parent], nums[ind]);
            // Recursively heapify up from the parent's position.
            heapify_up(nums, parent);
        }
    }

    // Function to update the value at index 'ind' and then adjust the heap accordingly.
    // If the new value is greater, the element is moved downward.
    // If the new value is smaller, the element is moved upward.
    void heapify(vector<int>& nums, int ind, int val) {
        // If the value is unchanged, no need to adjust the heap.
        if (nums[ind] == val) return;

        // If the new value is greater than the current value, adjust downward.
        if (nums[ind] < val) { 
            nums[ind] = val;
            heapify_down(nums, ind);
        } else { 
            // If the new value is smaller than the current value, adjust upward.
            nums[ind] = val;
            heapify_up(nums, ind);
        }
    }
};

// Example Usage:
int main() {
    // Create a min-heap represented as a vector.
    vector<int> heap = {1, 3, 5, 7, 9, 11, 13};
    Solution sol;
    
    // Print the heap before updating.
    cout << "Before heapify: ";
    for (int num : heap) cout << num << " ";
    cout << endl;

    // Update the element at index 2 to a new value (0) and adjust the heap.
    sol.heapify(heap, 2, 0);

    // Print the heap after updating.
    cout << "After heapify: ";
    for (int num : heap) cout << num << " ";
    cout << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(log2N) (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 log2N.
• Space Complexity:O(log2N)
  • The recursive stack space will contribute to log2N in the worst-case. There is no extra space used other than this as the array is modified in-place.