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.
About the Author
