Computer Sciences > GATE 2025 SET-1 > Heaps
The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node.
Suppose a Min-Heap T stores 32 keys. The height of T is ______ (Answer in integer)
Suppose a Min-Heap T stores 32 keys. The height of T is ______ (Answer in integer)
Correct : 5
Given: Min-Heap with 32 keys
Min-Heap structure:
A Min-Heap is a complete binary tree where every node is smaller than its children.
Formula for height of complete binary tree
For a complete binary tree with n nodes:
Height (h) = ⌊log₂(n)⌋
where ⌊ ⌋ means floor function (round down)
Calculating the height
Number of nodes (n) = 32
Height = ⌊log₂(32)⌋
Height = ⌊log₂(2⁵)⌋
Height = ⌊5⌋
Height = 5
Verification:
A complete binary tree of height 5 has:
- Minimum nodes = 2⁵ = 32 nodes
- Maximum nodes = 2⁶ - 1 = 63 nodes
Since we have exactly 32 nodes, height = 5
Answer: 5
Similar Questions
An array is [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] heapified. Which one of the following options represents the first three elements in the heapified array...
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...
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...
Total Unique Visitors
Loading......