Heap / Priority Queue - DSA: Merge Two Binary Max Heaps | Is Binary Tree Heap | BST to Max Heap

This module covers three advanced problems on Heaps and Priority Queues: merging two binary max heaps, checking whether a binary tree is a valid max heap, and converting a Binary Search Tree (BST) into a max heap. Mastering these concepts solidifies foundational tree traversal, heap property maintenance, and pointer manipulation techniques crucial for graph algorithms and dynamic programming.

1. Problem 1: Merge Two Binary Max Heaps

Why Do We Need This?

When dealing with priority queues or data streams, you often encounter scenarios where two independent max heaps (represented as arrays) must be combined into a single unified max heap. A naive element-by-element insertion is inefficient when high-performance data aggregation is required.

Core Mental Model & Analogy

Imagine you have two independent boxes of sorted weights (Max Heaps). Instead of meticulously comparing elements one by one between boxes, you can simply dump both boxes into a single large container and re-organize the entire container from scratch using an efficient down-heap restructuring algorithm.

Naive vs. Better Approach

Step-by-Step Evolution (Optimized Approach)

1. Combine Arrays: Create a new dynamic vector (answer) and push all elements from the first max heap (a), then all elements from the second max heap (b).
2. Apply Step-Down Heapify: Convert the combined array into a valid max heap by starting from the last non-leaf node down to the root (0).

Implementation Code (C++)

#include <vector>
#include <algorithm>

class Solution {
private:
    void heapify(vector<int>& arr, int index, int n) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != index) {
            swap(arr[largest], arr[index]);
            heapify(arr, largest, n);
        }
    }

public:
    vector<int> mergeHeaps(vector<int>& a, vector<int>& b, int n, int m) {
        vector<int> answer;
        
        // Step 1: Copy elements from both heaps into a single array
        for (int i = 0; i < n; i++) {
            answer.push_back(a[i]);
        }
        for (int i = 0; i < m; i++) {
            answer.push_back(b[i]);
        }
        
        int totalSize = answer.size();
        
        // Step 2: Build heap using bottom-up approach (step-down heapify)
        for (int i = (totalSize / 2) - 1; i >= 0; i--) {
            heapify(answer, i, totalSize);
        }
        
        return answer;
    }
};

2. Problem 2: Check If a Binary Tree Is a Heap ("Is Binary Tree Heap")

Problem Definition

Given a binary tree, determine whether it satisfies two strict properties of a Max Heap:

1. Complete Binary Tree (CBT): Every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
2. Max Heap Order Property: Every parent node must have a value greater than or equal to its children (Parent >= Children).

The Complete Binary Tree (CBT) Indexing Trap

To verify if a tree is a complete binary tree without building an explicit array, we can use array-based indexing for binary trees (where the root is at index 0, left child is 2 * i + 1, and right child is 2 * i + 2).

• Key Insight: If we count the total number of nodes in the tree ($N$), a complete binary tree will never have a node assigned an index greater than or equal to $N$. If any node's computed index $\ge N$, the tree is not a complete binary tree.

Step-by-Step Validation Workflow

Implementation Code (C++)

class Solution {
private:
    int countNodes(struct Node* root) {
        if (root == NULL) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }

    bool isCBT(struct Node* root, int index, int totalNodes) {
        if (root == NULL) return true;
        
        // If index exceeds or equals total nodes, it's not a CBT
        if (index >= totalNodes) return false;
        
        return isCBT(root->left, 2 * index + 1, totalNodes) &&
               isCBT(root->right, 2 * index + 2, totalNodes);
    }

    bool isMaxOrder(struct Node* root) {
        // Leaf node check
        if (root->left == NULL && root->right == NULL) {
            return true;
        }
        
        // Only left child exists
        if (root->right == NULL) {
            return (root->data >= root->left->data) && isMaxOrder(root->left);
        }
        
        // Both children exist
        else {
            bool leftCheck = (root->data >= root->left->data) && isMaxOrder(root->left);
            bool rightCheck = (root->data >= root->right->data) && isMaxOrder(root->right);
            return leftCheck && rightCheck;
        }
    }

public:
    bool isHeap(struct Node* tree) {
        int totalNodes = countNodes(tree);
        
        // Check both CBT structure and Max-Heap order property
        if (isCBT(tree, 0, totalNodes) && isMaxOrder(tree)) {
            return true;
        }
        return false;
    }
};

3. Problem 3: Convert Binary Search Tree (BST) to Max Heap

Problem Statement & Constraints

Given a Binary Search Tree (BST), convert it into a Max Heap with the following structural guarantees:

1. The shape (structure) of the tree must remain unchanged.
2. Every parent node must be greater than its child nodes.
3. BST Property Mapping: In the resulting max heap, all elements in the left subtree must be smaller than elements in the right subtree.

Core Mental Model & Algorithmic Strategy

Real-Life Analogy: Imagine organizing a library where books are currently indexed by a strict alphabetical catalog (BST). To convert them into a priority reading list (Max Heap) while respecting relative tree positions, you first unroll all books into a sorted linear sequence (In-Order Traversal), then repack them back into the exact tree structure using a Post-Order Traversal fill strategy.

1. Step 1 (In-Order Traversal): Traverse the BST in-order to extract all node values into a sorted array (ascending order).
2. Step 2 (Post-Order Fill): Traverse the tree in Post-Order (Left -> Right -> Node) to populate node values from the sorted array. Because post-order visits child subtrees before parent nodes, smaller elements naturally flow to left/right branches while the largest elements populate parent positions.

Step-by-Step Flow Walkthrough

Implementation Code (C++)

#include <vector>

class Solution {
private:
    void inOrderTraversal(Node* root, vector<int>& arr) {
        if (root == NULL) return;
        inOrderTraversal(root->left, arr);
        arr.push_back(root->data);
        inOrderTraversal(root->right, arr);
    }

    void postOrderFill(Node* root, vector<int>& arr, int& index) {
        if (root == NULL) return;
        
        // Traverse Left Subtree
        postOrderFill(root->left, arr, index);
        
        // Traverse Right Subtree
        postOrderFill(root->right, arr, index);
        
        // Populate current node with sorted value and increment index
        root->data = arr[index++];
    }

public:
    void setToMaxHeap(Node* root) {
        vector<int> sortedElements;
        
        // Step 1: Extract elements in sorted order via In-Order
        inOrderTraversal(root, sortedElements);
        
        // Step 2: Refill tree using Post-Order traversal
        int index = 0;
        postOrderFill(root, sortedElements, index);
    }
};

4. Summary and Key Takeaways

• Merge Two Max Heaps: Combining two heaps is most efficiently accomplished in $O(N + M)$ time by concatenating the arrays and applying a bottom-up step-down heapify rather than using individual queue insertions.
• Complete Binary Tree (CBT) Verification: Utilizing array-based index mapping (2*i + 1, 2*i + 2) against total node count $N$ provides an elegant $O(N)$ validation check for binary tree structure.
• BST to Max Heap Conversion: By leveraging an In-Order Traversal to retrieve sorted elements followed by a Post-Order Traversal to fill nodes, we successfully transform a BST into a valid max heap without altering its structural topology.
• Time Complexity Efficiency: All examined algorithms operate within linear time bounds ($O(N)$ or $O(N + M)$), making them optimal for production-grade data processing.
• Reference Passing in Recursion: Passing tracking indices and accumulation vectors as references (int& index, vector<int>& ans) prevents memory overhead and ensures state consistency across recursive stack frames.