Heaps, Priority Queues and Data Structure Operations Practice Questions for GATE CS

Solve 30+ Heaps, Priority Queues and Data Structure Operations practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Heaps, Priority Queues and Data Structure Operations

Programming and Data Structures

Heaps, Priority Queues & DS Operations

From tree geometry to priority queue mastery.

Heap Structure, Height & Leaf Positions

Complete binary tree geometry, array indexing, height formula, identifying leaves. Highest weightage in this chapter.

Heap Construction & Array Validation

Build-heap procedure, heapify, checking if a given array forms a valid heap.

Priority Queue Operations & Heap Extrema

Insert, extract-min or extract-max, finding extreme elements, complexity analysis.

Meld Operations & Data Structure Complexity

Merging two heaps, comparing meld cost across data structures.

Heap Structure, Height and Leaf Positions

Heaps, Priority Queues & DS Operations › Topic 1

Heap Structure, Height & Leaf Positions

The shape of the heap determines everything you can do with it.

What you will learn here

Why a heap is a complete binary tree and what that shape guarantees
The exact array-to-tree index mapping (parent, left child, right child)
How to compute heap height from $n$ in one formula
Which indices are internal nodes vs leaves
Where extreme elements can hide in a heap

Heaps, Priority Queues and Data Structure Operations: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Programming and Data Structures NAT

A binary min-heap contains $20$ distinct elements. The maximum element can be stored at most in _____________ different positions in the underlying array.

Correct Answer:

Step-by-Step Solution

Key idea: In a min-heap, the maximum element must be at a leaf node. The number of leaves in a complete binary tree with $n$ nodes is $⌈ n /2 ⌉$ .

Step 1: Identify that in a min-heap, the maximum cannot be at an internal node (it would violate the heap property since children must be $\geq$ parent).

Step 2: Therefore, the maximum must be at a leaf.

Step 3: Count the leaves: $⌈ n /2 ⌉ = ⌈ 20/2 ⌉ = 10$ .

Answer: 10

Common trap: Using $⌊ n /2 ⌋ = 10$ gives the same answer for even $n$ , but for odd $n$ it would be wrong. Always use $⌈ n /2 ⌉$ for leaf count.

Question 2 · Programming and Data Structures NAT

A binary min-heap stores $128$ distinct elements. The height of this heap is _____________. (Answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct formula application question. The height of a complete binary tree with $n$ nodes is $h = ⌊ lo g_{2} n ⌋$ .

Step 1: Identify $n = 128$ .

Step 2: Apply the height formula: $h = ⌊ lo g_{2} 128 ⌋$ .

Step 3: Since $128 = 2^{7}$ , we have $lo g_{2} 128 = 7$ .

Step 4: Therefore, $h = ⌊ 7 ⌋ = 7$ .

Answer: 7

Common trap: Students often count levels instead of edges. A tree with height 7 has 8 levels (level 0 through level 7), but height counts edges, not nodes.

Question 3 · Programming and Data Structures NAT

In a binary max-heap containing $15$ distinct elements stored in a 1-based array, the maximum possible index of the second largest element is _____________.

Correct Answer:

3.00

Step-by-Step Solution

Key idea: This tests the structural constraint on where extreme elements can hide in a heap.

Step 1: In a max-heap, the largest element must be at the root (index $1$ ).

Step 2: The second largest element must be greater than all other elements except the root. Therefore, its parent must be the root. If its parent were any other node, that parent would be larger than the second largest element, which is a contradiction.

Step 3: The children of the root (index $1$ ) are at indices $2 (1) = 2$ and $2 (1) + 1 = 3$ .

Step 4: The second largest element must be at index $2$ or $3$ . The maximum possible index is $3$ .

Answer: 3

Common trap: Assuming the second largest element can be anywhere in the tree, or confusing it with the minimum element (which must be at a leaf).

Question 4 · Programming and Data Structures NAT

In a binary heap stored in an array with 0-based indexing, the left child of the element at index $4$ is at index _____________.

Correct Answer:

Step-by-Step Solution

Key idea: This tests the left child formula for 0-based indexing.

Step 1: Identify the indexing scheme: 0-based.

Step 2: Recall the left child formula for 0-based indexing: $left (i) = 2 i + 1$ .

Step 3: Substitute $i = 4$ : $left (4) = 2 (4) + 1 = 8 + 1 = 9$ .

Answer: 9

Common trap: Using the 1-based formula $2 i = 8$ , or using the right child formula $2 i + 2 = 10$ .

Question 5 · Programming and Data Structures MCQ

Consider the following assertion and reason regarding binary heaps stored in arrays:

Assertion (A): In a binary heap stored in a 0-based array, the right child of the element at index $4$ is at index $9$ .

Reason (R): The formula for the right child in 0-based indexing is $2 i + 2$ .

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is not the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: This tests the exact index formulas for 0-based indexing and the ability to verify an assertion.

Step 1: Evaluate Reason (R): The formula for the right child in 0-based indexing is indeed $2 i + 2$ . (R is True)

Step 2: Evaluate Assertion (A) using the formula from R:

For $i = 4$ , right child = $2 (4) + 2 = 8 + 2 = 10$ .

Step 3: The assertion claims the right child is at index $9$ . However, $9$ is actually the left child ( $2 i + 1 = 2 (4) + 1 = 9$ ). The assertion is false because it uses the 1-based right child formula ( $2 i + 1$ ) or the 0-based left child formula on a 0-based right child question.

Step 4: Conclusion: A is false, but R is true.

Answer: D

Question 6 · Programming and Data Structures NAT

Consider a binary max-heap stored in an array with 1-based indexing. The element at index $11$ has its parent at index _____________.

Correct Answer:

Step-by-Step Solution

Key idea: This tests the parent index formula for 1-based indexing.

Step 1: Identify the indexing scheme: 1-based.

Step 2: Recall the parent formula for 1-based indexing: $parent (i) = ⌊ i /2 ⌋$ .

Step 3: Substitute $i = 11$ : $parent (11) = ⌊ 11/2 ⌋ = ⌊ 5.5 ⌋ = 5$ .

Answer: 5

Common trap: Using the 0-based formula $⌊(i - 1) /2 ⌋ = ⌊ 10/2 ⌋ = 5$ happens to give the same answer here, but for odd indices it can differ. Always check which indexing is used.

Question 7 · Programming and Data Structures NAT

A binary min-heap with $101$ elements is stored in an array with 1-based indexing. The index of the first leaf node in this array is _____________.

Correct Answer:

51.00

Step-by-Step Solution

Key idea: This tests the boundary between internal nodes and leaf nodes in a heap array.

Step 1: Recall that in a 1-based array of size $n$ , the internal nodes occupy indices $1$ through $⌊ n /2 ⌋$ .

Step 2: Calculate the last internal node index for $n = 101$ :

$⌊ 101/2 ⌋ = ⌊ 50.5 ⌋ = 50$ .

Step 3: The leaf nodes start immediately after the last internal node.

First leaf index = $50 + 1 = 51$ .

Answer: 51

Common trap: Answering $50$ by simply computing $⌊ n /2 ⌋$ without adding $1$ . The formula $⌊ n /2 ⌋$ gives the last internal node, not the first leaf.

Question 8 · Programming and Data Structures MCQ

Which of the following is a necessary condition for an array to represent a valid binary heap?

A.
The array must satisfy the heap property (parent $\leq$ children for min-heap or parent $\geq$ children for max-heap)
B.
The array must be sorted in ascending or descending order
C.
The array length must be a power of 2
D.
All elements in the array must be distinct

Correct Answer:

Step-by-Step Solution

Key idea: A binary heap requires two properties: (1) structural property (complete binary tree shape) and (2) order property (heap property).

Step 1: Recall the definition of a binary heap. It must be a complete binary tree (structural) and satisfy the heap ordering (order property).

Step 2: The structural property is automatically satisfied by the array representation (level-order filling with no gaps).

Step 3: The order property requires that for every parent-child pair, the heap condition holds (parent $\leq$ children in min-heap, or parent $\geq$ children in max-heap).

Step 4: Evaluate options:

Option A: Correct. This is the heap property.
Option B: Incorrect. A heap is not fully sorted, only partially ordered.
Option C: Incorrect. Array length can be any positive integer.
Option D: Incorrect. Heaps can have duplicate elements.

Answer: A

Question 9 · Programming and Data Structures NAT

A complete binary tree has height $3$ . The minimum number of nodes it can have is _____________.

Correct Answer:

Step-by-Step Solution

Key idea: A complete binary tree of height $h$ has minimum nodes when only one node exists at the last level.

Step 1: Recall that height $h$ means the longest path from root to leaf has $h$ edges.

Step 2: Levels 0 through $h - 1$ must be completely full. Level $h$ must have at least one node.

Step 3: Nodes in levels 0 to $h - 1$ : $1 + 2 + 4 + \dots + 2^{h - 1} = 2^{h} - 1$ .

Step 4: Add 1 node at level $h$ : $(2^{h} - 1) + 1 = 2^{h}$ .

Step 5: For $h = 3$ : minimum nodes = $2^{3} = 8$ .

Answer: 8

Common trap: Answering $2^{h} - 1 = 7$ (forgetting the node at level $h$ ) or $2^{h + 1} - 1 = 15$ (all levels full).

Question 10 · Programming and Data Structures NAT

A binary heap stores $255$ distinct elements. The total number of levels in the underlying complete binary tree is _____________.

Correct Answer:

8.00

Step-by-Step Solution

Key idea: This is a direct formula application question that tests the distinction between height and number of levels.

Step 1: Identify the number of elements $n = 255$ .

Step 2: Compute the height of the complete binary tree using the formula $h = ⌊ lo g_{2} n ⌋$ .

$h = ⌊ lo g_{2} 255 ⌋ = ⌊ 7.99 ⌋ = 7$ .

Step 3: The levels in a tree are numbered from $0$ to $h$ . The total number of levels is $h + 1$ .

Total levels = $7 + 1 = 8$ .

Answer: 8

Common trap: Students often confuse height with the number of levels and answer $7$ . Remember that height counts edges, while levels count the actual layers of nodes.

Try a question

Login to view the complete practice questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Heaps, Priority Queues and Data Structure Operations Practice Questions for GATE CS

Chapter Roadmap: Heaps, Priority Queues and Data Structure Operations

Heaps, Priority Queues & DS Operations

Heap Structure, Height and Leaf Positions

Heap Structure, Height & Leaf Positions

Heaps, Priority Queues and Data Structure Operations: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit