Previously Asked GATE Questions on Binary Heap

Question 1: The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.

Answer: (a)

Question 2: In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time (GATE CS 2003)

a) Θ(n log n)
b) Θ(n)
c) Θ(log n)
d) Θ(1)

Answer: (d)

Explanation:The 7th smallest element must be in first 7 levels. Total number of nodes in any Binary Heap in first 7 levels is at most 1 + 2 + 4 + 8 + 16 + 32 + 64 which is a constant. Therefore we can always find 7th smallest element in Θ(1) time.

Question 3: The number of elements that can be sorted in Θ(logn) time using heap sort is

(a) Θ(1)
(b) Θ(sqrt(logn))
(c) Θ(Log n/(Log Log n))
(d) Θ(Log n)

Answer: (c)

Explanation: Time complexity of Heap Sort is Θ(mLogm) for m input elements. For m = Θ(Log n/(Log Log n)), the value of Θ(m * Logm) will be Θ( [Log n/(Log Log n)] * [Log (Log n/(Log Log n))] ) which will be Θ( [Log n/(Log Log n)] * [ Log Log n – Log Log Log n] ) which is Θ(Log n)

Question 4: A max-heap is a heap where the value of each parent is greater than or equal to the values of its children. Which of the following is a max-heap?

Answer: (B)
A binary tree is max-heap if it is a complete binary tree (A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible) and it follows the max-heap property (value of each parent is greater than or equal to the values of its children).

A) is not a max-heap because it is not a complete binary tree
B) is a max-heap because it is complete binary tree and follows max-heap property.
C) is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property.
D) is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property. There are many other nodes in this tree which violate max-heap property in this tree

Question 5: A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?
(a) 1, 3, 5, 6, 8, 9
(b) 9, 6, 3, 1, 8, 5
(c) 9, 3, 6, 8, 5, 1
(d) 9, 5, 6, 8, 3, 1

Answer: (d)

Question 6: Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?

(a) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(b) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(c) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(d) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Answer: (a)

Question 7: Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is: 

(a) Θ(logn) 
(b) Θ(LogLogn ) 
(c) Θ(n) 
(d) Θ(nLogn)

Answer: (b)

Explanation: The height of a Max Heap is Θ(logn). If we perform binary search for finding the correct position then we need to do Θ(LogLogn) comparisons.

Question 8: In a binary max heap containing n numbers, the smallest element can be found in time (GATE CS 2006)

(a) 0(n)
(b) O(logn)
(c) 0(loglogn)
(d) 0(1)

Answer: (a)

In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)

         12
        /  \
      /      \
    8         7
   / \        / \
 /     \    /     \
2      3   4       5

Question 9: A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

(a) 10, 8, 7, 3, 2, 1, 5
(b) 10, 8, 7, 2, 3, 1, 5
(c) 10, 8, 7, 1, 2, 3, 5
(d) 10, 8, 7, 5, 3, 2, 1

Answer: (a)

Question 10: Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

(a) 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
(b) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
(c) 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
(d) 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Answer: (b)

In the GATE Exam, understanding binary heaps is like having a secret weapon. Questions might ask you to pick the right tool for a job, and heaps are often the superheroes of quick and efficient data organization.