Heap questions look visual, but one wrong index formula or missed swap can spoil the answer. A heap orders only each parent against its own children, which is why 90, 40, 80, 10, 30, 70, 20 is a valid max-heap even though it is nowhere near sorted. Attempt all 12 questions before reading the explanations. For a structured route through arrays, trees and heaps, use Coding & DSA courses.
1. Fix the heap rules before attempting the MCQs
Cue | Rule | Trap |
|---|---|---|
Binary heap | It is a complete binary tree | It need not be a binary search tree |
Max-heap | Every parent is at least its children | The full array need not be descending |
Min-heap | Every parent is at most its children | The full array need not be ascending |
1-based array | Parent | Do not import 0-based formulas |
0-based array | Parent | The root is at index |
Heap height is Theta(log n). In a 1-based heap, leaves occupy indices floor(n/2)+1 through n. Validate only parent-child inequalities. For completeness and level-order array storage, read Binary Trees and Binary Search Trees.
2. Definition, parent indices and heap validation: Questions 1-3
Question 1. Recognise the structure
A complete binary tree in which the value at each node is at least as large as the values of its children is known as a:
(a) Binary search tree
(b) AVL tree
(c) Completely balanced tree
(d) Heap
Answer: (d) Heap. "Complete binary tree" gives the shape rule, while "at least as large as its children" gives max-heap order. Unlike a binary search tree, a heap needs no left-smaller, right-larger rule. Its last level may be partly filled from the left.
Question 2. Parent in a 1-based array
Consider a 1-based array representation of an n-element binary heap, where elements are stored from index 1 to index n. For a non-root element stored at index i (1 < i <= n), the index of its parent is:
(a) i - 1
(b) ⌊i / 2⌋
(c) ⌈i / 2⌉
(d) (i + 1) / 2
Answer: (b) floor(i/2). Parent 3 owns children 6 and 7, and both floor(6/2) and floor(7/2) give 3. For a 0-based array, use floor((i-1)/2) instead.
Question 3. Validate a max-heap array
Which one of the following sequences when stored in an array at locations A[1],...,A[10] forms a max-heap?
(a) 23, 17, 10, 6, 13, 14, 1, 5, 7, 12
(b) 23, 17, 14, 7, 13, 10, 1, 5, 6, 12
(c) 23, 17, 14, 6, 13, 10, 1, 5, 7, 15
(d) 23, 14, 17, 1, 10, 13, 16, 12, 7, 5
Answer: (b). Check indices 1 to 5: 23 >= 17,14; 17 >= 7,13; 14 >= 10,1; 7 >= 5,6; 13 >= 12. The violations are A: 10 < 14 at 3,6; C: 13 < 15 at 5,10; D: 1 < 12 at 4,8.
3. Sift-up insertion and resulting arrays: Questions 4-5
Question 4. Insert seven values into an empty max-heap
After inserting the following elements, in the given order, into an initially empty max heap, which array representation is obtained?
Elements: 20, 30, 70, 10, 5, 50, 80
(a) 80, 70, 50, 30, 20, 10, 5
(b) 5, 10, 20, 30, 50, 70, 80
(c) 70, 20, 80, 10, 5, 30, 50
(d) 80, 20, 70, 10, 5, 30, 50
Answer: (d). The arrays after each insertion are [20], [30,20], [70,20,30], [70,20,30,10], [70,20,30,10,5], and [70,20,50,10,5,30]. Insert 80 at index 7, swap it with 50, then with 70. The result is [80,20,70,10,5,30,50]. Option A is a valid max-heap, but this insertion order does not produce it.
Question 5. Follow a second insertion order
The elements 42,25,30,40,22,35,26 are inserted one by one in the given order into a max-heap. The resultant max-heap is sorted in an array implementation as
(a) <42,40,35,25,22,30,26>
(b) <42,35,40,22,25,30,26>
(c) <42,40,35,25,22,26,30>
(d) <42,35,40,22,25,26,30>
Answer: (a). Inserting 40 at index 4 swaps it with 25, producing <42,40,30,25>. Inserting 35 at index 6 swaps it with 30, producing <42,40,35,25,22,30>. The final 26 stays under 35, giving <42,40,35,25,22,30,26>.
4. Delete-max and bottom-up heapify: Questions 6-7
Question 6. Perform two delete operations
Given a binary-max heap. The elements are stored in an array as 25, 14, 16, 13, 10, 8, 12. What is the content of the array after two delete operations?
(a) 14,13,8,12,10
(b) 14,12,13,10,8
(c) 14,13,12,8,10
(d) 14,13,12,10,8
Answer: (c). Remove 25, move 12 to the root, and sift it below 16: [16,14,12,13,10,8]. Remove 16, move 8 to the root, then swap with 14 and 13: [14,13,12,8,10]. Delete-max replaces the root before sifting down; it does not shift entries left.
Question 7. Count the minimum interchanges
Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉 The minimum number of interchanges needed to convert it into a max-heap is
(a) 4
(b) 5
(c) 2
(d) 3
Answer: (d) 3. With 1-based indices, swap 15 with child 100 at index 6; swap 50 with the new child 100 at index 3; then swap root 89 with 100. The final heap is <100,19,89,17,12,50,2,5,7,11,6,9,15>. Other internal nodes already obey max-heap order.
5. Where extreme values can occur: Questions 8-9
Question 8. Find the maximum in a min-heap
Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?
(a) Θ(1)
(b) Θ(log n)
(c) Θ(n)
(d) Θ(n log n)
Answer: (c) Theta(n). A min-heap exposes the minimum but does not order its leaves. The maximum must be among roughly n/2 leaves, so an optimal algorithm scans them. The last leaf inspected may be the maximum, making the worst case linear.
Question 9. Count all possible maximum positions
Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of k is
(a) 53
(b) 52
(c) 27
(d) 1
Answer: (a) 53. floor(105/2) = 52, so the leaves occupy indices 53 through 105. Their count is 105 - 53 + 1 = 53. Any leaf can hold the distinct maximum without violating min-heap order.
6. Operation costs, linear heap construction and top-k use: Questions 10-12
Question 10. Worst-case priority-queue operations
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations. When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
(a) Both Extract-Max(A) and Insert(A,key) run in O(1).
(b) Both Extract-Max(A) and Insert(A,key) run in O(log(n)).
(c) Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n).
(d) Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)).
Answer: (b). Peeking is O(1), but extracting may sift the replacement through O(log n) levels. Insertion may sift a new leaf to the root. Both are O(log n) in the worst case.
Question 11. Build a heap bottom-up
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n - 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n - 1)/2⌋, ⌊(n - 3)/ 2⌋, ....., 0. The time required to construct a heap in this manner is
(a) O(log n)
(b) O(n)
(c) O(n log log n)
(d) O(n log n)
Answer: (b) O(n). Most nodes are near the leaves. Work is bounded by n(1/4 + 2/8 + 3/16 + ...), a convergent constant times n. Bottom-up construction is linear; separate insertions can take O(n log n). For that sum written out term by term, read Binary Heaps for GATE: Build-Heap, Heapify and Deletion Numericals Solved.
Question 12. Keep the top 10 from one million values
Which data structure is most efficient to find the top 10 largest items out of 1 million items stored in a file?
(a) Min heap
(b) Max heap
(c) BST
(d) Sorted array
Answer: (a) Min heap. Hold the 10 best values seen so far in a min-heap, so its root is the smallest of those ten, and compare every later value against that root. If the root is 742, a next value of 615 loses the comparison and is dropped without touching the heap, while a next value of 901 replaces 742 and sifts down. One million comparisons against a ten-element heap is O(1,000,000 log 10) time and O(10) extra space, which is why a max-heap of all one million values is the wasteful answer here.
7. Answer strip, diagnosis and next practice step
Answer strip: 1-D, 2-B, 3-B, 4-D, 5-A, 6-C, 7-D, 8-C, 9-A, 10-B, 11-B, 12-A.
Misses in Questions 1-3 show a definition or indexing gap. Revisit sift-up for 4-5, sift-down for 6-7, leaf boundaries for 8-9, and complexity for 10-12.
Use this 20-minute correction loop:
Redraw Questions 4, 6 and 7 without looking at the options.
Write the 0-based and 1-based parent-child formulas once.
Explain in one sentence why Question 11 is linear and Question 12 uses a min-heap.
Finish with the broader Data Structures MCQs set.
The short version
Write the array convention down before you start, then follow a single leaf-to-root or root-to-leaf path and count the swaps as you go. Keep peeking at the root (O(1)) separate from extracting it (O(log n)), and remember that a min-heap pins only its minimum: its maximum can sit at any leaf. For systematic study, use DSA using Java.
