⛰️ Heaps & Priority Queues
Why it matters: Building a heap, counting swaps and recognising valid heaps are repeated question types; heaps also power heap sort and Dijkstra.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 3 done.
Formulas
Indices (0-based)
left = 2i + 1; right = 2i + 2; parent = ⌊(i − 1)/2⌋. 1-based: 2i, 2i + 1, ⌊i/2⌋
Height / levels
height = ⌊log₂ n⌋; at most ⌈n / 2^(h+1)⌉ nodes of height h
Build-heap
Floyd (bottom-up): Θ(n); repeated insert: Θ(n log n)
Operations
insert O(log n); extract-max O(log n); find-max O(1); delete arbitrary known index O(log n)
Leaves
a heap of n nodes has ⌈n/2⌉ leaves
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Is this array a valid max-heap? / after insertions
Check each parent against its children, or insert keys one by one and read the array.
★★★
Heap after build-heap or delete-max
Simulate heapify on a small array and read a particular index.
★★★
Where can the minimum / maximum be?
Position of the minimum in a max-heap: among the leaves.
★★★
Time complexity of heap operations
Build heap O(n), k-th largest, merging heaps.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
9 real questions from the official GATE CSE papers (2013 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
9 questions · 0 correct of 0 attempted · marks 0 / 16
Year:
GATE 2025 CS1 · Q35NAT1 mark
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 ______.
GATE 2024 CS1 · Q41MCQ2 marks
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?
GATE 2024 CS1 · Q43MCQ2 marks
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
GATE 2023 · Q12MCQ1 mark
Which one of the following sequences when stored in an array at locations A[1], …, A[10] forms a max-heap?
GATE 2023 · Q46MCQ2 marks
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?
GATE 2020 · Q47NAT2 marks
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ______.
GATE 2018 · Q46NAT2 marks
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ______.
GATE 2016 Set 1 · Q37MCQ2 marks
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
GATE 2013 Code A · Q30MCQ2 marks
The number of elements that can be sorted in Θ(log n) time using heap sort is
Common traps
The smallest element of a max-heap is at a leaf, not necessarily the last position.
Floyd and insertion-based builds can give different arrays from the same input.
The 1-based and 0-based child formulas differ: read which one the question uses.
Searching for an arbitrary element in a heap is O(n).