Merge 2 MaxHeaps

#include <bits/stdc++.h> // Includes common standard libraries (vector, iostream, algorithm for swap)
using namespace std;     // Use the standard namespace

// Function to perform heapify operation for a Max Heap.
// It ensures that the subtree rooted at 'index' satisfies the Max Heap property.
// 'arr': The vector representing the heap (passed by reference to allow modification).
// 'index': The 0-based index of the root of the subtree to heapify.
// 'size': The current logical size of the heap (number of valid elements in 'arr').
// Time Complexity: O(log N) where N is the current 'size' of the heap.
// Space Complexity: O(H) for recursion stack (where H is the height of the subtree).
void heapify(vector<int> &arr, int index, int size) {
    int largest = index;      // Assume current node 'index' is the largest.
    int left = 2 * index + 1; // 0-based index of left child.
    int right = 2 * index + 2; // 0-based index of right child.

    // Check if left child exists within bounds and its value is greater than arr[largest].
    if(left < size && arr[largest] < arr[left]) {
        largest = left; // If so, left child is the new candidate for largest.
    }

    // Check if right child exists within bounds and its value is greater than arr[largest].
    // (Note: 'largest' might have been updated to 'left' in the previous step).
    if(right < size && arr[largest] < arr[right]) {
        largest = right; // If so, right child is the new candidate for largest.
    }

    // If 'largest' is not the original 'index', it means a child was larger.
    if(largest != index) {
        swap(arr[index], arr[largest]);     // Swap current node with the largest child.
        heapify(arr, largest, size);       // Recursively call heapify on the affected subtree
                                         // to ensure property is maintained downwards.
    }
}

// Function to merge two arrays (or heaps) into a single Max Heap.
// It does this by concatenating the arrays and then building a Max Heap from the result.
// Time Complexity: O(N + M) where N = arr1.size() and M = arr2.size().
// Space Complexity: O(N + M) for the new combined vector.
vector<int> mergeHeaps(vector<int> arr1, vector<int> arr2) {
    // Step 1: Concatenate arr2 into arr1.
    // This effectively puts all elements into a single vector.
    for(auto i : arr2) {
        arr1.push_back(i);
    }

    // Step 2: Build a Max Heap from the combined array (arr1).
    // Iterate from the last non-leaf node down to the root (index 0).
    // For 0-based indexing, non-leaf nodes are from (size/2 - 1) to 0.
    // This bottom-up approach is the most efficient way to build a heap (O(N) time).
    for(int i = arr1.size() / 2 - 1; i >= 0; i--) {
        heapify(arr1, i, arr1.size()); // Apply heapify to each non-leaf node.
    }

    // Return the newly formed Max Heap.
    return arr1;
}

int main() {
    vector<int> arr1, arr2;

    // Input elements for the first array.
    cout << "Enter the elements of first array (enter -1 to stop) : ";
    int temp;
    cin >> temp;
    while(temp != -1) {
        arr1.push_back(temp);
        cin >> temp;
    }

    // Input elements for the second array.
    cout << "Enter the elements of second array (enter -1 to stop) : ";
    cin >> temp;
    while(temp != -1) {
        arr2.push_back(temp);
        cin >> temp;
    }

    // Call the mergeHeaps function to get the combined Max Heap.
    vector<int> result = mergeHeaps(arr1, arr2);

    // Print the elements of the merged heap.
    cout << "Merged heap : ";
    for(int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

/*
Example Usage:

Input 1: 42 37 35 25 29 21 -1
Input 2: 93 34 65 11 -1

Combined Array initially: [42, 37, 35, 25, 29, 21, 93, 34, 65, 11] (size = 10)

Building Max Heap from combined array (i = (10/2)-1 = 4 down to 0):

i = 4 (value 29): Children 2*4+1=9 (11), 2*4+2=10(out). Largest 29. No change.
i = 3 (value 25): Children 2*3+1=7 (34), 2*3+2=8 (65). Largest 65. Swap 25, 65.
    Array: [42, 37, 35, 65, 29, 21, 93, 34, 25, 11]
    Heapify(arr, 8, 10) (on new 25): Children 2*8+1=17(out). No change.
i = 2 (value 35): Children 2*2+1=5 (21), 2*2+2=6 (93). Largest 93. Swap 35, 93.
    Array: [42, 37, 93, 65, 29, 21, 35, 34, 25, 11]
    Heapify(arr, 6, 10) (on new 35): Children 2*6+1=13(out). No change.
i = 1 (value 37): Children 2*1+1=3 (65), 2*1+2=4 (29). Largest 65. Swap 37, 65.
    Array: [42, 65, 93, 37, 29, 21, 35, 34, 25, 11]
    Heapify(arr, 3, 10) (on new 37): Children 2*3+1=7 (34), 2*3+2=8 (25). Largest 37. No change.
i = 0 (value 42): Children 2*0+1=1 (65), 2*0+2=2 (93). Largest 93. Swap 42, 93.
    Array: [93, 65, 42, 37, 29, 21, 35, 34, 25, 11]
    Heapify(arr, 2, 10) (on new 42): Children 2*2+1=5 (21), 2*2+2=6 (35). Largest 42. No change.

Merged Heap (Example Output): [93 65 42 37 29 21 35 34 25 11] (Order may vary slightly but will be a valid Max Heap)
*/

1. Problem Statement: Merging Two Heaps

• Given two collections of elements, often presented as arrays that might or might not already be heaps, the goal is to combine them into a single data structure that adheres to the heap property (either Max Heap or Min Heap).
• The provided code implements merging two arrays into a single Max Heap.

2. Approach: Simple Concatenation and Build Heap

• Core Idea: The most straightforward and efficient way to merge two heaps (or arrays that you want to form a heap from) is to:
  1. Combine all elements from both input structures into a single array.
  2. Then, apply the “Build Heap” algorithm on this newly formed combined array.
• Build Heap Algorithm:
  • To convert an arbitrary array into a heap (Max or Min), we iterate through all non-leaf nodes in reverse order (from the last non-leaf node up to the root) and apply the heapify operation on each.
  • This bottom-up approach ensures that when heapify is called on a node, its children’s subtrees have already been heapified.
  • For 0-based indexing, the last non-leaf node is at index (total_size / 2) - 1.

3. heapify(vector<int> &arr, int index, int size) Function

• Purpose: This helper function restores the Max Heap property for a subtree rooted at index within the arr (of size). It assumes its children’s subtrees are already valid Max Heaps.
• Indexing: Uses 0-based indexing for child calculations:
  • Left child: 2 * index + 1
  • Right child: 2 * index + 2
• Logic (“Percolate Down”):
  1. Initialize largest = index.
  2. Compare arr[largest] with arr[left] (if left is valid and arr[left] is larger). Update largest.
  3. Compare arr[largest] (potentially updated) with arr[right] (if right is valid and arr[right] is larger). Update largest.
  4. If largest is no longer index (meaning a child was larger), swap arr[index] with arr[largest] and recursively call heapify on the subtree where the swap occurred (heapify(arr, largest, size)).
• Time Complexity: O(log K) where K is the size of the subtree being heapified.

4. mergeHeaps(vector<int> arr1, vector<int> arr2) Function

• Purpose: Merges two input vectors (potentially representing heaps) into a single Max Heap vector.
• Steps:
  1. Concatenation: Iterates through arr2 and push_backs each element into arr1. After this loop, arr1 contains all elements from both original arrays.
  2. Build Heap:
     • The for loop for(int i = arr1.size()/2 - 1; i >= 0; i--) iterates from the last non-leaf node’s index down to the root (index 0).
     • For each such i, heapify(arr1, i, arr1.size()) is called to correctly position the element at arr1[i] and its subtree to satisfy the Max Heap property.
• Time Complexity: O(N + M)
  • Appending arr2 to arr1: O(M) (where M is arr2.size()).
  • Building heap on N+M elements: O(N + M) (where N is arr1.size() initially).
  • Total: O(N + M).
• Space Complexity: O(N + M)
  • The input arr1 and arr2 are passed by value, creating copies.
  • The combined arr1 grows to N+M elements.

---