chapter

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

Heaps, Priority Queues and Data Structure Operations notes for GATE CS: 46 study cards covering concepts, formulas, shortcuts and exam traps, plus solved prac

heaps priority queues and data structure operations notes

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. 1 Heap Structure, Height & Leaf Positions Complete binary tree geometry, array indexing, height formula, identifying leaves. Highest weightage in this chapter. 2 Heap Construction & Array Validation Build-heap procedure, heapify, checking if a given array forms a valid heap. 3 Priority Queue Operations & Heap Extrema Insert, extract-min or extract-max, finding extreme elements, complexity analysis. 4 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

What Makes a Binary Heap?

Two Rules Define a Binary Heap A binary heap is a data structure that satisfies two properties simultaneously: 1. Structural Property — Complete Binary Tree Every level except possibly the last is completely full. The last level has all nodes pushed as far left as possible. No gaps are allowed in the last level. 2. Order Property — Heap Property Min-heap: parent \leq child for every node. Max-heap: parent \geq child for every node. The structural property is what we focus on in this topic. It gives the heap a predictable, rigid shape that we can describe with simple arithmetic on indices. Because the shape is rigid, we do not need pointers. A plain array is enough — the position in the array encodes the parent-child relationships.

43 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

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

Question 2

Level 1: Warm-up

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

Question 3

Level 1: Warm-up

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 _____________.

Question 4

Level 1: Warm-up

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

Question 5

Level 1: Warm-up

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 .

Question 6

Level 1: Warm-up

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

Question 7

Level 1: Warm-up

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 _____________.

Question 8

Level 1: Warm-up

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

Question 9

Level 1: Warm-up

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

Question 10

Level 1: Warm-up

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

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

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

Heaps, Priority Queues and Data Structure Operations notes for GATE CS: 46 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

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

What Makes a Binary Heap?

Two Rules Define a Binary Heap

A binary heap is a data structure that satisfies two properties simultaneously:

1. Structural Property — Complete Binary Tree

Every level except possibly the last is completely full.
The last level has all nodes pushed as far left as possible.
No gaps are allowed in the last level.

2. Order Property — Heap Property

Min-heap: $parent \leq child$ for every node.
Max-heap: $parent \geq child$ for every node.

The structural property is what we focus on in this topic. It gives the heap a predictable, rigid shape that we can describe with simple arithmetic on indices.

Because the shape is rigid, we do not need pointers. A plain array is enough — the position in the array encodes the parent-child relationships.

The Complete Binary Tree Shape

Levels in a Complete Binary Tree

A complete binary tree fills level by level, left to right:

Level	Maximum nodes at that level
0	$1 = 2^{0}$
1	$2 = 2^{1}$
2	$4 = 2^{2}$
3	$8 = 2^{3}$
$h$	$2^{h}$

Total nodes if all levels $0$ through $h$ are full:

$1 + 2 + 4 + \dots + 2^{h} = 2^{h + 1} - 1$

This formula is the foundation for computing height. If you know $n$ , you can reverse-engineer which level the last node sits on, and that gives you the height.

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.

heaps priority queues and data structure operations notes

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

What Makes a Binary Heap?

Two Rules Define a Binary Heap

Try a question

Login to view the complete notes

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 Notes 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

What Makes a Binary Heap?

Two Rules Define a Binary Heap

The Complete Binary Tree Shape

Levels in a Complete Binary Tree

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 notes in this unit