Programming and Data Structures · Binary Heaps
Official IIT answer key · IISc Bangalore · Audited Aug 2026
GATE CSE 2016 Set 1 Q37 · MCQ · 2 marks
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?Key concept
No account needed
Sit 5 related Binary HeapsPYQs as a guest. We'll score the set and show which traps cost marks — sign in only if you want to save the run.
Topic notes
Binary heaps are tested frequently in GATE CS with a strong focus on structural and array properties (complete binary tree indexing), operation trace (insertion bubbling up and bottom-up build-heap sift-down), and extreme value locations (finding maximum in min-heap or minimum in max-heap). Questions vary from direct index/leaf counting formulas and tree height calculations to asymptotic complexities of priority queue operations. Recent years exhibit an increased prevalence of NAT and MSQ questions testing index ranges and structural properties.
Full Binary Heaps guide →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?
Topic-wise GATE CS PYQs with verified steps
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.