Heaps, Priority Queues and Data Structure Operations PYQs for GATE CS

Solve 8+ Heaps, Priority Queues and Data Structure Operations previous year 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 (8 Problems)

Question 1 · Programming and Data Structures · 2026_Set1 MSQ

Let

n

be an odd number greater than 100. Consider a binary minheap with

n

elements stored in an array

P

whose index starts from 1.

Which of the following indices of

P

do/does NOT correspond to any leaf node of the minheap?

A.
$\frac{n + 1}{2}$
B.
$\frac{n - 1}{2}$
C.
$\frac{n - 3}{2}$
D.
$n$

Question 2 · Programming and Data Structures · 2025_Set2 MCQ

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:

P: Unsorted doubly linked list with pointers to the head node and tail node of the list.

Q: Min-heap implemented using an array.

R: Binary Search Tree.

Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size

n

of these data structures?

A.
P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n)$
B.
P: $Θ (1)$ , Q: $Θ (n lo g n)$ , R: $Θ (n)$
C.
P: $Θ (n)$ , Q: $Θ (n lo g n)$ , R: $Θ (n^{2})$
D.
P: $Θ (1)$ , Q: $Θ (n)$ , R: $Θ (n lo g n)$

Question 3 · Programming and Data Structures · 2025_Set1 NAT

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)

Correct Answer:

5.00

Step-by-Step Solution

Insight: This is a direct application of the heap height formula. The height of a complete binary tree with $n$ nodes is simply $⌊ lo g_{2} n ⌋$ .

Exam route: The problem states the min-heap stores 32 keys. Using the height formula $h = ⌊ lo g_{2} n ⌋$ , we substitute $n = 32$ . Since $32 = 2^{5}$ , $lo g_{2} 32 = 5$ . The floor of 5 is 5. The height is 5.

Learning route:

Understand the definition: The height of a rooted tree is the maximum number of edges on any path from the root to a leaf.
Recall the structure of a heap: A heap is a complete binary tree. This means all levels except possibly the last are completely full, and the last level is filled from left to right.
Apply the formula: For a complete binary tree with $n$ nodes, the height $h$ is given by $h = ⌊ lo g_{2} n ⌋$ .
Calculate: Here, $n = 32$ . We know that $2^{5} = 32$ , so $lo g_{2} 32 = 5$ .
Conclusion: The height of the min-heap is 5.

Question 4 · Programming and Data Structures · 2024_Set1 MCQ

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$

Correct Answer:

Step-by-Step Solution

Insight: In a min-heap, the maximum element must be located at one of the leaf nodes. The problem reduces to finding the total number of leaf nodes in a complete binary tree with 105 nodes.

Exam route:

A min-heap is a complete binary tree. The maximum element can never be an internal node because an internal node must be smaller than or equal to its children. Thus, the maximum must be a leaf.
For a complete binary tree with $n$ nodes, the number of leaf nodes is $⌈ n /2 ⌉$ .
Substitute $n = 105$ . The number of leaves is $⌈ 105/2 ⌉ = ⌈ 52.5 ⌉ = 53$ .
Since all elements are distinct, the maximum element could be any of these 53 leaves. Thus, there are 53 possible values for the index $k$ .

Learning route:

Understand the min-heap property: Every parent is less than or equal to its children.
Deduce the location of the maximum: If the maximum element were at an internal node, it would have to be less than or equal to its children. But it is the maximum, so it cannot be strictly less than any element. This implies it cannot have any children. Therefore, it must be a leaf.
Count the leaves: In a complete binary tree represented as an array of size $n$ , the leaves occupy the indices from $⌊ n /2 ⌋ + 1$ to $n$ .
Calculate the count: The number of leaves is $n - ⌊ n /2 ⌋ = ⌈ n /2 ⌉$ .
Apply to $n = 105$ : $⌈ 105/2 ⌉ = 53$ .

Question 5 · Programming and Data Structures · 2024_Set1 MCQ

An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?

A.
82, 90, 101
B.
82, 11, 93
C.
131, 11, 93
D.
131, 111, 90

Correct Answer:

Step-by-Step Solution

Insight: This is a heap construction question. The array must be converted into a max-heap. We need to apply the Build-Max-Heap procedure and observe the first three elements.

Exam route:

The array is $A = [82, 101, 90, 11, 111, 75, 33, 131, 44, 93]$ .
The maximum element is 131. In a max-heap, the root must be the maximum. So $A [1]$ will be 131. This eliminates options A and B.
We apply Max-Heapify from the last internal node down to the root. The last internal node is at index $⌊ 10/2 ⌋ = 5$ .
After running the full Build-Max-Heap algorithm, the root becomes 131. Through careful tracing, we find the array starts with 131, 111, 90.

Learning route:

Identify the goal: Convert the given array into a max-heap.
Locate internal nodes: For $n = 10$ , internal nodes are at indices 1 to 5. We start heapifying from index 5 down to 1.
Index 5 (val 111): Children are at 10 (val 93). $111 > 93$ , so no swap.
Index 4 (val 11): Children are at 8 (131) and 9 (44). Max child is 131. Swap 11 and 131. Array becomes: $[82, 101, 90, 131, 111, 75, 33, 11, 44, 93]$ .
Index 3 (val 90): Children are at 6 (75) and 7 (33). $90 > 75, 33$ , so no swap.
Index 2 (val 101): Children are at 4 (131) and 5 (111). Max child is 131. Swap 101 and 131. Array: $[82, 131, 90, 101, 111, 75, 33, 11, 44, 93]$ . Now heapify index 4 (val 101): children 8 (11), 9 (44). Swap 101 and 44. Array: $[82, 131, 90, 44, 111, 75, 33, 11, 101, 93]$ .
Index 1 (val 82): Children are at 2 (131) and 3 (90). Max child is 131. Swap 82 and 131. Array: $[131, 82, 90, 44, 111, 75, 33, 11, 101, 93]$ . Now heapify index 2 (val 82): children 4 (44), 5 (111). Swap 82 and 111. Array: $[131, 111, 90, 44, 82, 75, 33, 11, 101, 93]$ . Now heapify index 5 (val 82): child 10 (93). Swap 82 and 93. Array: $[131, 111, 90, 44, 93, 75, 33, 11, 101, 82]$ .
The first three elements are 131, 111, 90.

Question 6 · Programming and Data Structures · 2023 MCQ

Which one of the following sequences when stored in an array at locations $A [1], \dots, 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

Correct Answer:

Step-by-Step Solution

Insight: This is a heap validation question. We need to check which of the given arrays satisfies the max-heap property: every parent must be greater than or equal to its children.

Exam route:

The max-heap property requires $A [i] \geq A [2 i]$ and $A [i] \geq A [2 i + 1]$ for all valid $i$ .
We can quickly eliminate options by checking small values of $i$ .
Check Option A: At $i = 3$ , $A [3] = 10$ . Its children are $A [6] = 14$ and $A [7] = 1$ . Since $10 < 14$ , this violates the max-heap property. Eliminate A.
Check Option C: At $i = 5$ , $A [5] = 13$ . Its child is $A [10] = 15$ . Since $13 < 15$ , this violates the property. Eliminate C.
Check Option D: At $i = 4$ , $A [4] = 1$ . Its children are $A [8] = 12$ and $A [9] = 7$ . Since $1 < 12$ , this violates the property. Eliminate D.
Check Option B: Every internal node is greater than or equal to its children. Specifically, 23>=17,14; 17>=7,13; 14>=10,1; 7>=5,6; and 13>=12. Option B satisfies all conditions.

Learning route:

Understand the max-heap property: For every node $i$ (from 1 to $⌊ n /2 ⌋$ ), its value must be greater than or equal to the values of its left child ( $2 i$ ) and right child ( $2 i + 1$ ), if they exist.
Systematically check each option. It is often faster to look for violations rather than verifying every single node.
A violation occurs if any parent is strictly less than any of its children.
By checking the internal nodes (indices 1 to 5 for a 10-element array), we can quickly identify which arrays are invalid max-heaps.

Question 7 · Programming and Data Structures · 2023 MCQ

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 (lo g (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 (lo g (n))$ .

Correct Answer:

Step-by-Step Solution

Insight: This is a standard complexity question for heap-based priority queues. The key is to distinguish between finding the extreme element (which is $O (1)$ ) and extracting it while maintaining the heap property (which is $O (lo g n)$ ).

Exam route: Recall the fundamental operations of a binary heap. The maximum element is always at the root, so finding it takes $O (1)$ time. However, Extract-Max removes the root, moves the last element to the root, and performs a heapify-down operation to restore the max-heap property. This traversal goes down the height of the tree, taking $O (lo g n)$ time. Insert adds an element at the end and performs a heapify-up, which also takes $O (lo g n)$ time. Therefore, both operations run in $O (lo g n)$ worst-case time.

Learning route:

Identify the data structure: A max-heap implemented priority queue.
Analyze Extract-Max: The max element is at index 1. We swap it with the last element, reduce the heap size, and call Max-Heapify on the root. Max-Heapify takes time proportional to the height of the tree, which is $O (lo g n)$ .
Analyze Insert: We append the new key at the end of the array and bubble it up by comparing with its parent. This also takes time proportional to the height, $O (lo g n)$ .
Conclusion: Both operations have a worst-case running time of $O (lo g n)$ .

Question 8 · Programming and Data Structures · 2021_Set2 MCQ

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.
$Θ (lo g n)$
C.
$Θ (n)$
D.
$Θ (n lo g n)$

Try a question

Login to view the complete previous-year 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 PYQs 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 (8 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit