Binary Heaps MCQs in Data Structure
Binary Heaps MCQs with Solutions
1.
A max-heap is a complete binary tree in which:
A. Parent is smaller than children
B. Parent is greater than or equal to children
C. Left child is always greater than right child
D. Heap is not ordered
Answer: B
Solution:
Max-heap property: each parent ≥ its children.
2.
The minimum number of nodes in a binary heap of height 4 = ?
A. 8
B. 16
C. 15
D. 10
Answer: C
Solution:
Minimum nodes = 2^h = 2^4 = 16? Actually, minimum occurs when last level partially filled → minimum nodes = 2^h = 16 (consider height counted from 0).
3.
In a heap stored as array, left child of node at index i (0-based) = ?
A. i/2
B. 2i
C. 2i + 1
D. 2i − 1
Answer: C
Solution:
Left child = 2i + 1, right child = 2i + 2 (0-based array).
4.
Parent of node at index i in a 0-based heap array = ?
A. i/2
B. (i−1)/2
C. 2i + 1
D. 2i − 1
Answer: B
Solution:
Parent = floor((i−1)/2).
5.
Time complexity of insertion in a binary heap of n nodes = ?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer: B
Solution:
Insertion → bubble-up → height = log n → O(log n).
6.
Time complexity of deleting the max element in a max-heap = ?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer: B
Solution:
Delete root → replace with last node → heapify → O(log n).
7.
Maximum number of nodes at level i in a heap = ?
A. i²
B. 2^i
C. 2^(i−1)
D. i+1
Answer: B
Solution:
Level i (root at 0) → maximum 2^i nodes.
8.
A heap with 15 nodes has how many leaf nodes?
A. 7
B. 8
C. 6
D. 9
Answer: B
Solution:
Leaf nodes = ceil(n/2) = ceil(15/2) = 8.
9.
Heap sort’s worst-case time complexity = ?
A. O(n²)
B. O(n log n)
C. O(n)
D. O(log n)
Answer: B
Solution:
Heap sort → build heap O(n) + extract n elements × O(log n) = O(n log n).
10.
Heap can be used to implement:
A. Priority queue
B. Dictionary
C. Hash table
D. Stack
Answer: A
Solution:
Heaps efficiently implement priority queues.
11.
In max-heap, which of the following is always true?
A. Root = minimum
B. Root = maximum
C. Last node = maximum
D. Heap is sorted
Answer: B
Solution:
Max-heap → root holds the maximum.
12.
Building a heap from an unordered array of n elements → time complexity:
A. O(n log n)
B. O(n)
C. O(log n)
D. O(n²)
Answer: B
Solution:
Heapify bottom-up → O(n) time complexity.
13.
Heap of height h → maximum nodes = ?
A. 2^h
B. 2^(h+1) − 1
C. h²
D. 2h
Answer: B
Solution:
Complete binary tree → 2^(h+1) − 1 nodes.
14.
Heap of n elements is represented in an array. Index of last element = ?
A. n
B. n−1
C. n+1
D. n/2
Answer: B
Solution:
0-based indexing → last index = n−1.
15.
In a min-heap, deleting minimum element requires:
A. Replace root with last node + bubble-up
B. Replace root with last node + heapify
C. Replace last node with root + heapify
D. Random deletion
Answer: B
Solution:
Delete root → replace with last → bubble-down (heapify).
16.
Max-heap property: child ≤ parent. True/False?
A. True
B. False
Answer: A
Solution:
By definition, max-heap parent ≥ children.
17.
Min-heap of 31 nodes → number of leaf nodes = ?
A. 15
B. 16
C. 14
D. 17
Answer: B
Solution:
Leaf nodes = ceil(n/2) = ceil(31/2) = 16.
18.
Which of the following is not possible in a heap?
A. Random search in O(1)
B. Insertion in O(log n)
C. Extract max/min in O(log n)
D. Heapify in O(n)
Answer: A
Solution:
Heap → no direct random access to find an arbitrary element in O(1).
19.
Time complexity of searching a particular element in heap = ?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
Answer: B
Solution:
Heap is not ordered for arbitrary search → O(n).
20.
Number of levels in heap with n nodes = ?
A. log₂ n
B. log₂(n+1)
C. n
D. √n
Answer: B
Solution:
Height h = floor(log₂ n) → levels = h+1 = floor(log₂(n)) + 1 ≈ log₂(n+1).
21.
In max-heap, if root = 100, left child = 50, right child = 60, what is heap after deleting root?
A. 60 root, 50 child
B. 50 root, 60 child
C. 60 root, 100 child
D. 50 root, 100 child
Answer: A
Solution:
Delete root → replace with last → bubble-down → largest child becomes root → 60.
22.
Heap of 15 nodes → index of left child of node at index 5?
A. 10
B. 11
C. 12
D. 9
Answer: B
Solution:
Left child = 2i + 1 = 2×5 + 1 = 11.
23.
Heap represented as array → index of right child of node 6?
A. 12
B. 13
C. 14
D. 11
Answer: B
Solution:
Right child = 2i + 2 = 2×6 + 2 = 14 → wait, let’s recalc: 2*6+2=14 ✅
24.
After inserting 45 in max-heap [100, 50, 60, 30, 40, 20], the heap = ?
A. [100, 50, 60, 30, 40, 20, 45]
B. [100, 50, 60, 30, 40, 45, 20]
C. [100, 50, 60, 45, 40, 20, 30]
D. [100, 50, 60, 30, 45, 20, 40]
Answer: A
Solution:
Insert → last position → bubble-up if parent < inserted node → 45 < 60 → no swap → [100,50,60,30,40,20,45].
25.
Heapify at root for max-heap [10, 20, 15, 30, 40] → root after heapify = ?
A. 40
B. 30
C. 20
D. 15
Answer: A
Solution:
Heapify → largest child 40 → root becomes 40 → heap property restored.
26.
Max-heap [90, 50, 80, 30, 40, 20, 70] → after inserting 85, root = ?
A. 90
B. 85
C. 100
D. 80
Answer: A
Solution:
Insert 85 at last position → bubble-up: 85 < 80? 85 > 80 → swap → new root = 90 → heap property maintained.
27.
Min-heap [10, 15, 20, 30, 40, 25] → delete root → new root = ?
A. 15
B. 20
C. 25
D. 30
Answer: A
Solution:
Replace root with last node 25 → bubble-down → swap with smaller child 15 → root = 15.
28.
Number of leaf nodes in a heap of 63 nodes = ?
A. 31
B. 32
C. 30
D. 33
Answer: B
Solution:
Leaf nodes = ceil(n/2) = ceil(63/2) = 32.
29.
Heap of height 4 → maximum nodes = ?
A. 15
B. 31
C. 16
D. 32
Answer: B
Solution:
Max nodes = 2^(h+1) − 1 = 2^5 − 1 = 31.
30.
Heapify operation in max-heap is called:
A. Bubble-up
B. Bubble-down
C. Insertion
D. Deletion
Answer: B
Solution:
Heapify = bubble-down to restore max-heap property.
31.
Heap represented as array → parent of node at index 12 = ?
A. 5
B. 6
C. 7
D. 4
Answer: A
Solution:
Parent = floor((i−1)/2) = floor((12−1)/2) = floor(11/2) = 5.
32.
Heap sort in ascending order uses:
A. Max-heap
B. Min-heap
C. Binary search tree
D. AVL tree
Answer: A
Solution:
Extract max repeatedly → sorted ascending.
33.
Heap of 31 nodes → last level starts at index = ?
A. 15
B. 16
C. 17
D. 14
Answer: B
Solution:
Last level nodes = ceil(n/2) = ceil(31/2) = 16 → index = 16 (0-based 15).
34.
Time complexity to build heap from unordered array of 16 elements = ?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
Answer: B
Solution:
Bottom-up heapify → linear time O(n).
35.
Heap property violated if:
A. Parent < child in max-heap B. Parent > child in max-heap
C. Children unordered in max-heap
D. Root maximum in max-heap
Answer: A
Solution:
Max-heap → parent must be ≥ children.
36.
Number of levels in a heap with 100 nodes = ?
A. 6
B. 7
C. 8
D. 9
Answer: C
Solution:
Height = floor(log₂ n) = floor(log₂ 100) ≈ 6 → levels = height + 1 = 7.
37.
Heapify is required after:
A. Insertion at last
B. Deletion of root
C. Both A & B
D. None
Answer: C
Solution:
Insertion → bubble-up, deletion → bubble-down → heapify needed.
38.
Heap represented as array [50, 40, 45, 30, 35, 20, 25] → insert 42 → new heap = ?
A. [50, 42, 45, 40, 35, 20, 25, 30]
B. [50, 42, 45, 30, 35, 20, 25, 40]
C. [50, 40, 45, 30, 35, 20, 25, 42]
D. [50, 45, 42, 30, 35, 20, 25, 40]
Answer: A
Solution:
Insert 42 → last position → bubble-up → swap with 40 → heap maintained.
39.
Deleting max element from max-heap [100, 90, 80, 70, 60] → new root = ?
A. 90
B. 80
C. 70
D. 60
Answer: A
Solution:
Delete root → replace with last 60 → bubble-down → swap with larger child 90 → root = 90.
40.
Max-heap of 15 nodes → last level indices = ?
A. 7–14
B. 8–15
C. 7–15
D. 8–14
Answer: A
Solution:
Last level starts at ceil(n/2) → 8th node (index 7) → indices 7–14.
41.
Heap of n elements → maximum height = ?
A. log₂ n
B. n−1
C. n
D. 2 log₂ n
Answer: B
Solution:
Degenerate heap (all right children) → height = n−1.
42.
Min-heap [10, 15, 20, 30, 25] → insert 5 → new root = ?
A. 5
B. 10
C. 15
D. 20
Answer: A
Solution:
Insert 5 → bubble-up → root updated → min-heap property restored.
43.
Heap sort complexity:
A. O(n²)
B. O(n log n)
C. O(n)
D. O(log n)
Answer: B
Solution:
Build heap O(n) + n extractions × O(log n) = O(n log n).
44.
Heap represented as array → index of right child of node 7 = ?
A. 14
B. 15
C. 13
D. 16
Answer: A
Solution:
Right child = 2i + 2 = 2×7 + 2 = 16 (0-based).
45.
Heap of 100 nodes → number of internal nodes = ?
A. 50
B. 49
C. 48
D. 51
Answer: B
Solution:
Internal nodes = floor(n/2) = floor(100/2) = 50? Wait, internal = n − leaf nodes = 100 − ceil(100/2) = 100 − 50 = 50.
46.
Heap insertion may require maximum swaps = ?
A. log₂ n
B. n
C. n/2
D. √n
Answer: A
Solution:
Insertion → bubble-up → max log₂ n swaps.
47.
Heapify at index i in max-heap → time complexity = ?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
Answer: A
Solution:
Bubble-down along height → O(log n).
48.
Heap property violated after insertion of 120 in max-heap root 100 → fix requires:
A. Swap with root
B. Bubble-up until root
C. Bubble-down
D. No swap
Answer: B
Solution:
Insert → bubble-up → node may reach root.
49.
Binary heap is:
A. Complete binary tree
B. Full binary tree
C. BST
D. AVL tree
Answer: A
Solution:
Heap = complete binary tree, partially filled last level.
50.
Heap sort descending → use:
A. Max-heap
B. Min-heap
C. BST
D. AVL
Answer: B
Solution:
Extract min repeatedly → descending sorted array.
51.
Min-heap → smallest element always at:
A. Root
B. Leaf
C. Leftmost node
D. Rightmost node
Answer: A
Solution:
Min-heap property → root holds minimum.
52.
Max-heap root = 200, children = 150, 180 → delete root → new root = ?
A. 180
B. 150
C. 200
D. 150 or 180
Answer: A
Solution:
Delete root → replace with last node 180 → bubble-down → largest child becomes root.
53.
Heapify bottom-up builds heap in:
A. O(n²)
B. O(n log n)
C. O(n)
D. O(log n)
Answer: C
Solution:
Bottom-up heap construction → linear time.
54.
Heap with n nodes → number of comparisons for extract-max worst-case = ?
A. log₂ n
B. n
C. n log n
D. 1
Answer: A
Solution:
Extract max → bubble-down along height → log₂ n comparisons.
55.
Heap represented as array → parent of node at index 15 = ?
A. 7
B. 6
C. 8
D. 14
Answer: A
Solution:
Parent = floor((i−1)/2) = floor((15−1)/2) = floor(14/2) = 7.
56.
Heap insertion → worst-case time complexity = ?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
Answer: B
Solution:
Insertion → bubble-up along height → O(log n).
57.
Heap of 7 nodes → leaf nodes = ?
A. 3
B. 4
C. 5
D. 2
Answer: B
Solution:
Leaf nodes = ceil(n/2) = ceil(7/2) = 4.
58.
Max-heap [100, 80, 90, 50, 60, 40] → insert 85 → root = ?
A. 100
B. 85
C. 90
D. 80
Answer: A
Solution:
Insert 85 → bubble-up → 85 < 90 → bubble-up stops → root unchanged.
59.
Heap represented as array [10, 15, 20, 30, 40] → build max-heap → root = ?
A. 40
B. 30
C. 20
D. 15
Answer: A
Solution:
Build max-heap → largest element 40 → root.
60.
Heap of n nodes → height = ?
A. log₂ n
B. n
C. n/2
D. √n
Answer: A
Solution:
Complete binary tree → height = floor(log₂ n).
61.
Max-heap [90, 80, 70, 60, 50, 40, 30] → after inserting 85 → new heap = ?
A. [90, 85, 70, 80, 50, 40, 30, 60]
B. [90, 80, 85, 60, 50, 40, 30, 70]
C. [90, 85, 70, 60, 80, 40, 30, 50]
D. [90, 80, 85, 60, 50, 40, 30, 70]
Answer: D
Solution:
Insert 85 → last position → bubble-up → swap with parent if necessary → heap property maintained.
62.
Min-heap [10, 15, 20, 25, 30, 35, 40] → insert 5 → new root = ?
A. 10
B. 5
C. 15
D. 20
Answer: B
Solution:
Insert 5 → bubble-up → reaches root → root = 5.
63.
Heap of 31 nodes → number of internal nodes = ?
A. 16
B. 15
C. 14
D. 17
Answer: B
Solution:
Internal nodes = n − leaf nodes = 31 − ceil(31/2) = 31 − 16 = 15.
64.
Heap sort ascending → array initially [40, 10, 20, 30, 15] → first extracted element = ?
A. 10
B. 15
C. 20
D. 40
Answer: D
Solution:
Max-heap → root = maximum → first extracted = 40.
65.
Max-heap → number of swaps in insertion worst-case = ?
A. log₂ n
B. n
C. 2 log₂ n
D. 1
Answer: A
Solution:
Insertion → bubble-up → worst-case swaps = height = log₂ n.
66.
Heap of 100 nodes → number of leaf nodes = ?
A. 50
B. 51
C. 49
D. 52
Answer: B
Solution:
Leaf nodes = ceil(n/2) = ceil(100/2) = 50 → double-check: last level partially filled → 51 leaf nodes.
67.
Heapify at index i in max-heap → time complexity = ?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
Answer: A
Solution:
Heapify → bubble-down along height → O(log n).
68.
Heap represented as array [100, 90, 80, 70, 60, 50, 40] → delete root → new heap = ?
A. [90, 70, 80, 40, 60, 50]
B. [90, 70, 80, 50, 60, 40]
C. [80, 70, 90, 50, 60, 40]
D. [90, 80, 70, 50, 60, 40]
Answer: B
Solution:
Delete root → replace with last node 40 → bubble-down → largest child swaps → heap property restored.
69.
Heap of 15 nodes → last level node indices = ?
A. 7–14
B. 8–15
C. 7–15
D. 8–14
Answer: A
Solution:
Last level starts at ceil(n/2) → indices 7–14 (0-based).
70.
Heap insertion → worst-case time complexity = ?
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
Answer: B
Solution:
Bubble-up along height → O(log n).
71.
Min-heap → root deletion → new root replaced with last element → operation called:
A. Bubble-up
B. Bubble-down (heapify)
C. Swap
D. Rebuild
Answer: B
Solution:
Delete root → last element replaces root → bubble-down to restore heap property.
72.
Heap represented as array → left child of node index 10 = ?
A. 20
B. 21
C. 22
D. 19
Answer: B
Solution:
Left child = 2i + 1 = 2×10 + 1 = 21.
73.
Heap property violated → operation to restore = ?
A. Insertion
B. Heapify
C. Deletion
D. Traversal
Answer: B
Solution:
Heapify restores max/min-heap property after insertion/deletion.
74.
Heap sort descending → use:
A. Max-heap
B. Min-heap
C. BST
D. AVL
Answer: B
Solution:
Min-heap → extract min repeatedly → sorted descending.
75.
Heap of 50 nodes → max height = ?
A. 5
B. 6
C. 7
D. 8
Answer: C
Solution:
Height = floor(log₂ n) = floor(log₂ 50) ≈ 5 → max height = 5 → levels = 6 → height = 5.
76.
Max-heap → root = 100, children = 90, 80 → delete root → new root = ?
A. 90
B. 80
C. 100
D. 85
Answer: A
Solution:
Delete root → last node 80 replaces → bubble-down → largest child 90 becomes root.
77.
Heap insertion → element placed initially at:
A. Root
B. Leaf (last)
C. Middle
D. Any random position
Answer: B
Solution:
Insert at last position → bubble-up.
78.
Heap of 31 nodes → number of swaps to heapify root = ?
A. 1
B. log₂ 31 ≈ 5
C. 31
D. 2
Answer: B
Solution:
Heapify → swaps along height → log₂ n = 5 swaps maximum.
79.
Heap of n nodes → number of null child pointers = ?
A. n
B. n+1
C. n−1
D. 2n
Answer: B
Solution:
Complete binary tree → null child links = n + 1.
80.
Heap represented as array → right child of index 7 = ?
A. 14
B. 15
C. 13
D. 16
Answer: B
Solution:
Right child = 2i + 2 = 2×7 + 2 = 16 → 0-based → index = 16.
81.
Max-heap → number of leaf nodes = ?
A. ceil(n/2)
B. floor(n/2)
C. n/3
D. log₂ n
Answer: A
Solution:
Leaf nodes = ceil(n/2).
82.
Heap of 20 nodes → number of internal nodes = ?
A. 9
B. 10
C. 11
D. 12
Answer: B
Solution:
Internal nodes = n − leaf nodes = 20 − ceil(20/2) = 20 − 10 = 10.
83.
Heap → worst-case search complexity = ?
A. O(log n)
B. O(n)
C. O(1)
D. O(n log n)
Answer: B
Solution:
Heap not ordered for arbitrary search → linear search required → O(n).
84.
Heap of n elements → height = log₂ n. True/False?
A. True
B. False
Answer: A
Solution:
Complete binary tree → height ≈ log₂ n.
85.
Heap of 10 nodes → last level indices = ?
A. 4–9
B. 5–9
C. 6–10
D. 5–10
Answer: B
Solution:
Last level starts at ceil(n/2) = ceil(10/2) = 5 → indices 5–9.
86.
Max-heap → extract-max → complexity = ?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
Answer: B
Solution:
Bubble-down along height → O(log n).
87.
Heap sort → first step:
A. Build heap
B. Extract max/min
C. Swap elements
D. Insert elements
Answer: A
Solution:
Heap sort → build heap first → then repeatedly extract max/min.
88.
Heap represented as array → parent of index 12 = ?
A. 6
B. 5
C. 7
D. 8
Answer: B
Solution:
Parent = floor((i−1)/2) = floor((12−1)/2) = 5.
89.
Min-heap → root deletion → new root replaced by:
A. First element
B. Last element
C. Middle element
D. Random element
Answer: B
Solution:
Replace root with last element → bubble-down → maintain min-heap.
90.
Heap insertion → number of swaps in best-case = ?
A. 0
B. 1
C. log₂ n
D. n
Answer: A
Solution:
Best-case → inserted element ≤ parent → no swaps.
91.
Heap sort → ascending → uses which heap type?
A. Max-heap
B. Min-heap
C. Binary tree
D. BST
Answer: A
Solution:
Max-heap → repeatedly extract max → ascending sorted array.
92.
Heap of 31 nodes → height = ?
A. 4
B. 5
C. 6
D. 7
Answer: B
Solution:
Height = floor(log₂ 31) = 4 → levels = height +1 = 5.
93.
Heap → number of swaps in deletion worst-case = ?
A. log₂ n
B. n
C. 2 log₂ n
D. 1
Answer: A
Solution:
Bubble-down along height → max swaps = log₂ n.
94.
Heap represented as array → index of left child of index 14 = ?
A. 28
B. 29
C. 27
D. 30
Answer: B
Solution:
Left child = 2i + 1 = 2×14 + 1 = 29.
95.
Heap insertion may require number of swaps = ?
A. log₂ n
B. n
C. n²
D. 1
Answer: A
Solution:
Insertion → bubble-up along height → max log₂ n swaps.
96.
Heap of 100 nodes → number of internal nodes = ?
A. 50
B. 49
C. 48
D. 51
Answer: A
Solution:
Internal nodes = n − leaf nodes = 100 − ceil(100/2) = 50.
97.
Heap sort → time complexity = ?
A. O(n²)
B. O(n log n)
C. O(n)
D. O(log n)
Answer: B
Solution:
Heap sort → build heap O(n) + n extractions × O(log n) = O(n log n).
98.
Heap → after insertion → operation used to restore property = ?
A. Bubble-up
B. Bubble-down
C. Swap
D. Rebuild
Answer: A
Solution:
Insertion → bubble-up to maintain heap property.
99.
Heap → after deletion → operation used = ?
A. Bubble-down
B. Bubble-up
C. Swap
D. None
Answer: A
Solution:
Delete root → last element replaces root → bubble-down (heapify).
100.
Heap → maximum nodes at level 3 = ?
A. 8
B. 4
C. 2
D. 16
Answer: A
Solution:
Level i → max nodes = 2^i → 2³ = 8.