Heap / Priority Queue: Advanced Interview Problems & Algorithmic Patterns

This comprehensive guide covers advanced heap and priority queue interview problems, breaking down time complexities, edge cases, implementation trade-offs, and optimal coding strategies for coding rounds (GFG, InterviewBit, LeetCode).

1. Why Do We Need Advanced Heap Problem-Solving Patterns?

The Core Dilemma

When presented with a coding problem, developers often struggle with choosing the right underlying data structure:

• Should I use a Sorted Array?
• Or should I use a Heap / Priority Queue?

By mastering the upcoming problem patterns, you will instantly recognize when to leverage Heaps versus sorted structures to optimize time complexity from $O(N^2)$ down to $O(N \log N)$ or $O(\log N)$.

2. Problem 1: Height of a Heap

Problem Statement

Given an array representing a Min-Heap of size $N$, compute the height of the heap.

Creator's Real-Life Analogy & Height Definition

Note: Always pay strict attention to how the creator or interviewer defines "Height".

• In standard tree theory, height is sometimes counted by nodes.
• In this specific problem, Height is defined as the number of edges along the longest path from the root node to any leaf node.

For example, a single node has 0 edges (height = 0). Two nodes (root and one child) have 1 edge (height = 1).

Naive vs. Optimal Approach

• Naive Approach: Build an explicit tree data structure from the array ($O(N)$ time) and traverse down to find the longest path ($O(N)$ time).
• Optimal Mathematical Approach: Notice how heap height increases at powers of 2 ($2^0, 2^1, 2^2, 2^3, \dots, 2^h = N$). By repeatedly dividing the size $N$ by 2 until it reaches 1, we count the number of divisions, which yields $\lfloor \log_2 N \rfloor$.

Step-by-Step Evolution & Code Implementation

We handle the base edge case where $N = 1$ (height = 1 per problem constraints) and iteratively divide $N$ by 2.

long long getHeightOfHeap(long long n) {
    if (n == 1) return 1;
    long long height = 0;
    while (n > 1) {
        height++;
        n /= 2;
    }
    return height;
}

• Time Complexity: $O(\log N)$
• Space Complexity: $O(1)$

3. Problem 2: Minimum Cost of Ropes

Problem Statement

Given an array of rope lengths, connect all ropes into a single rope. Connecting two ropes of lengths $A$ and $B$ incurs a cost of $(A + B)$. Find the minimum total cost to connect all ropes.

Core Mental Model & Greedy Strategy

To minimize the total cumulative cost, we must always greedily combine the two smallest available ropes first. Combining large ropes early drastically inflates the cumulative cost because those large values get re-added multiple times in subsequent connection steps.

Naive Array Approach vs. Min-Heap Priority Queue

Complete Flow Walkthrough

Code Implementation

#include <queue>
#include <vector>

long long minCost(vector<long long>& arr) {
    priority_queue<long long, vector<long long>, greater<long long>> minHeap(arr.begin(), arr.end());
    long long totalCost = 0;
    
    while (minHeap.size() > 1) {
        long long first = minHeap.top();
        minHeap.pop();
        
        long long second = minHeap.top();
        minHeap.pop();
        
        long long combined = first + second;
        totalCost += combined;
        
        minHeap.push(combined);
    }
    
    return totalCost;
}

4. Problem 3: Magician and Chocolates

Problem Statement

You are given $N$ bags, each containing a certain number of chocolates. You have $A$ seconds. In each second, you can choose any bag, eat all the chocolates inside it, and the magician will refill that bag with $\lfloor chocolates / 2 \rfloor$ chocolates. Find the maximum total chocolates you can eat in $A$ seconds. Return the result modulo $10^9 + 7$.

Greedy Strategy & Max-Heap Model

• To maximize the total chocolates eaten, we must always pick the bag with the maximum number of chocolates at every second.
• Why Max-Heap? We need $O(\log N)$ extraction of the maximum element and $O(\log N)$ re-insertion of the halved value.

Edge Cases & Production Safeguards

1. Integer Overflow: The total sum of chocolates can exceed standard 32-bit integer limits. Always accumulate sums and answers using long long.
2. Zero Chocolate Bags: If a bag's chocolate count drops such that $\lfloor count / 2 \rfloor == 0$, pushing zero back into the heap wastes operations and can cause infinite loops or redundant checks. Always verify that top / 2 > 0 before pushing.

Code Implementation

#include <queue>
#include <vector>

long long nchoc(int A, vector<int>& B) {
    priority_queue<int> maxHeap(B.begin(), B.end());
    long long maxChocolates = 0;
    long long MOD = 1000000007;
    
    while (A > 0 && !maxHeap.empty()) {
        int curr = maxHeap.top();
        maxHeap.pop();
        
        maxChocolates = (maxChocolates + curr) % MOD;
        
        int refilled = curr / 2;
        if (refilled > 0) {
            maxHeap.push(refilled);
        }
        A--;
    }
    
    return maxChocolates;
}

5. Problem 4: Last Stone Weight

Problem Statement

We have a collection of stones, each with a given integer weight. Each turn, we choose the two heaviest stones and smash them together.

• If weights $x$ and $y$ ($x \le y$) collide:
  • If $x == y$, both stones are completely destroyed.
  • If $x \neq y$, the stone of weight $x$ is destroyed, and the stone of weight $y$ has its weight reduced to $y - x$.
• At the end, return the weight of the last remaining stone. If no stones remain, return 0.

Algorithmic Blueprint

1. Insert all stone weights into a Max-Heap.
2. While the heap size is greater than 1:
   • Extract the largest stone ($Y$).
   • Extract the second largest stone ($X$).
   • If $Y > X$, push $(Y - X)$ back into the Max-Heap.
3. If the heap is empty, return 0. Otherwise, return maxHeap.top().

Code Implementation

#include <queue>
#include <vector>

int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> maxHeap(stones.begin(), stones.end());
    
    while (maxHeap.size() > 1) {
        int y = maxHeap.top();
        maxHeap.pop();
        
        int x = maxHeap.top();
        maxHeap.pop();
        
        if (y > x) {
            maxHeap.push(y - x);
        }
    }
    
    return maxHeap.empty() ? 0 : maxHeap.top();
}

6. Problem 5: Profit Maximization

Problem Statement

You manage a stadium with multiple rows. You are given an array representing the number of vacant seats in each row. You need to sell tickets to $B$ people. Each ticket sold costs an amount equal to the number of vacant seats currently available in that row, after which the vacant seat count for that row decrements by 1. Maximize your total profit.

Mental Model & Heap Selection

• To maximize revenue, sell each ticket from the row currently having the maximum vacant seats.
• Because selling a ticket reduces the seat count by 1, we must update the row's capacity and re-insert it into a Max-Heap.
• Dual Operations: Both deletion (extracting max) and insertion (updating count minus 1) occur every step. Therefore, a Max-Heap ($O(\log N)$ per operation) is vastly superior to a sorted array ($O(N)$ shift per operation).

Code Implementation

#include <queue>
#include <vector>

int solve(vector<int>& A, int B) {
    priority_queue<int> maxHeap(A.begin(), A.end());
    long long totalProfit = 0;
    
    while (B > 0 && !maxHeap.empty()) {
        int vacant = maxHeap.top();
        maxHeap.pop();
        
        totalProfit += vacant;
        
        if (vacant - 1 > 0) {
            maxHeap.push(vacant - 1);
        }
        B--;
    }
    
    return totalProfit;
}

7. Summary and Key Takeaways

• When to Use Heaps: Whenever a problem requires repeatedly finding, extracting, and updating the minimum or maximum element dynamically, use a Priority Queue (Heap).
• Height of a Heap: Calculated efficiently in $O(\log N)$ time via successive integer divisions by 2 ($\lfloor \log_2 N \rfloor$), respecting edge-to-edge path definitions.
• Min-Cost Ropes Greedy Pattern: Always combine the two smallest elements first to minimize cumulative addition penalties ($O(N \log N)$ time).
• Max-Heap Chocolate & Profit Pattern: Greedily extract the largest element, process the operation, halve or decrement the value, and push it back if greater than zero.
• Insertion vs. Deletion Performance:
  • Pure deletion tasks can sometimes use sorted arrays, but hybrid problems involving both deletion and re-insertion mandate Heaps to avoid catastrophic $O(N^2)$ array-shifting bottlenecks.
• Overflow Prevention: Always utilize long long accumulators for cumulative costs, profits, and modular arithmetic outputs in production environments.