PPractick

The problem

A monitoring tool receives a priority queue's internal array from another service and must validate it before trusting it: does the array satisfy the min-heap property? In array form, node i's children are at 2i + 1 and 2i + 2, so the check is simply that every parent is ≤ each child that exists. Only the first half of the array has children, so the loop can stop at index n/2 − 1.

Example: [10, 15, 14, 25, 30] → true; [2, 1] → false.

Function signature

bool isMinHeap(const vector<int>& a);

Test cases

Input	Output	Explanation
[10, 15, 14, 25, 30]	true
[30, 56, 22, 49, 30, 51, 2, 67]	false	30 > 22 at the root
[1, 2, 3, 4, 5, 6]	true	A sorted array is always a min-heap
[2, 1]	false
[3, 3, 3]	true	Equal values are allowed
[5]	true

(Confirm: the array is a complete binary tree in level order; equal parent and child values are allowed.)

How interviewers phrase it

• "Given an array, check whether it represents a binary heap" (GeeksforGeeks "Does array represent Heap", in its max-heap form; the min-heap version flips the comparison).

Clarifying questions to ask

1. Min-heap or max-heap?
2. Is equality allowed between parent and child? (Yes.)
3. Is the array guaranteed to be complete? (Yes: arrays represent complete trees by construction.)

Follow-ups to expect

1. "Which indices have children?"
2. "Why is checking parent against child enough?"
3. "Recursive version?"
4. "Standard library?"
5. "Complexity?"

Related questions

• Minimize Max Distance to Gas Station Hard
• Find the number that appears once, and other numbers twice Medium
• Longest subarray with given sum K (positives) Medium
• Longest subarray with sum K Medium
• Sort an array of 0's 1's and 2's Medium
• Kadane's Algorithm Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in