Heaps, Priority Queues and Data Structure Operations Short Notes for GATE CS
Heaps, Priority Queues and Data Structure Operations short notes for GATE CS: 10 study cards covering concepts, formulas, shortcuts and exam traps, plus solve
heaps priority queues and data structure operations short notes
Heap Structure Toolkit — Final Summary
Final Revision — Heap Structure, Height, Leaves
Height
h=⌊log2n⌋
Index formulas (1-based)
Parent of i: ⌊i/2⌋
Left child of i: 2i
Right child of i: 2i+1
Node classification
Internal nodes: indices 1 to ⌊n/2⌋
Leaf nodes: indices ⌊n/2⌋+1 to n
Number of leaves: ⌈n/2⌉
Extreme element locations
Min-heap: minimum at root (index 1), maximum at some leaf
Max-heap: maximum at root (index 1), minimum at some leaf
Possible positions for the opposite extreme: ⌈n/2⌉
Quick checks
Height counts edges, not nodes.
Always confirm 0-based vs 1-based indexing.
For odd n: ⌊n/2⌋=(n−1)/2.
Formula Matrix
Formula Matrix
A[i]≥A[2i]∧A[i]≥A[2i+1]Cond: 1≤i≤⌊N/2⌋
i←⌊N/2⌋ down to 1Cond: 1-based indexing
O(N)Cond: Bottom-up Floyd build-heap
∑hi<NCond: hi is height of node i
T(n)=(Ln−1)T(L)T(R)Cond: L,R are subtree sizes
⌈N/2h+1⌉Cond: Nodes at height h
If You See This, Do This
If You See This, Do This
"forms a valid max-heap"Check A[i]≥ children for i≤⌊N/2⌋
"heapified array"Sift-down from ⌊N/2⌋ to 1
"exact number of swaps"Count physical data movements only
"partial heapify"Sift-down only ⌊N/2⌋…k
"distinct max-heaps"Apply (Ln−1)T(L)T(R)
"time complexity"O(N), reject O(NlogN)
7 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 2i+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 short 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.
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.
Heaps, Priority Queues and Data Structure Operations Short Notes for GATE CS
Heaps, Priority Queues and Data Structure Operations short notes for GATE CS: 10 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.
Heap Structure Toolkit — Final Summary
Final Revision — Heap Structure, Height, Leaves
Height
h=⌊log2n⌋
Index formulas (1-based)
Parent of i: ⌊i/2⌋
Left child of i: 2i
Right child of i: 2i+1
Node classification
Internal nodes: indices 1 to ⌊n/2⌋
Leaf nodes: indices ⌊n/2⌋+1 to n
Number of leaves: ⌈n/2⌉
Extreme element locations
Min-heap: minimum at root (index 1), maximum at some leaf
Max-heap: maximum at root (index 1), minimum at some leaf
Possible positions for the opposite extreme: ⌈n/2⌉
Quick checks
Height counts edges, not nodes.
Always confirm 0-based vs 1-based indexing.
For odd n: ⌊n/2⌋=(n−1)/2.
Formula Matrix
Formula Matrix
A[i]≥A[2i]∧A[i]≥A[2i+1]Cond: 1≤i≤⌊N/2⌋
i←⌊N/2⌋ down to 1Cond: 1-based indexing
O(N)Cond: Bottom-up Floyd build-heap
∑hi<NCond: hi is height of node i
T(n)=(Ln−1)T(L)T(R)Cond: L,R are subtree sizes
⌈N/2h+1⌉Cond: Nodes at height h
If You See This, Do This
If You See This, Do This
"forms a valid max-heap"Check A[i]≥ children for i≤⌊N/2⌋
"heapified array"Sift-down from ⌊N/2⌋ to 1
"exact number of swaps"Count physical data movements only
"partial heapify"Sift-down only ⌊N/2⌋…k
"distinct max-heaps"Apply (Ln−1)T(L)T(R)
"time complexity"O(N), reject O(NlogN)
Traps and Invariants
Traps and Invariants
Build-heap is O(NlogN) via N insertions.
Check: Nodes at bottom have height 0, sum is geometric O(N).
Validate by checking only root or assuming sorted array.
Check: Audit every internal node to ⌊N/2⌋; siblings need not be sorted.
Stop sift-down after first swap or swap with smaller child.
Check: Trace continuously to leaf; swap with larger child for max-heap.
Heaps, Priority Queues and Data Structure Operations: Solved Questions with Step-by-Step Explanations (10 Problems)
Question 1 · Programming and Data StructuresNAT
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:
10
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 ≥ 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 StructuresNAT
A binary min-heap stores 128 distinct elements. The height of this heap is _____________. (Answer in integer)
Correct Answer:
7
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=⌊log2n⌋.
Step 1: Identify n=128.
Step 2: Apply the height formula: h=⌊log2128⌋.
Step 3: Since 128=27, we have log2128=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 StructuresNAT
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 StructuresNAT
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:
9
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)=2i+1.
Step 3: Substitute i=4: left(4)=2(4)+1=8+1=9.
Answer: 9
Common trap: Using the 1-based formula 2i=8, or using the right child formula 2i+2=10.
Question 5 · Programming and Data StructuresMCQ
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 2i+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:
D
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 2i+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 (2i+1=2(4)+1=9). The assertion is false because it uses the 1-based right child formula (2i+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 StructuresNAT
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:
5
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⌋.
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 StructuresNAT
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 StructuresMCQ
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 ≤ children for min-heap or parent ≥ 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:
A
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 ≤ children in min-heap, or parent ≥ 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 StructuresNAT
A complete binary tree has height 3. The minimum number of nodes it can have is _____________.
Correct Answer:
8
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+⋯+2h−1=2h−1.
Step 4: Add 1 node at level h: (2h−1)+1=2h.
Step 5: For h=3: minimum nodes = 23=8.
Answer: 8
Common trap: Answering 2h−1=7 (forgetting the node at level h) or 2h+1−1=15 (all levels full).
Question 10 · Programming and Data StructuresNAT
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=⌊log2n⌋.
h=⌊log2255⌋=⌊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.