GATE Questions & Answers of Binary heaps

What is the Weightage of Binary heaps in GATE Exam?

Total 12 Questions have been asked from Binary heaps topic of Programming and Data Structures subject in previous GATE papers. Average marks 1.67.

Consider the following statements:

  I.    The smallest element in a max-heap is always at a leaf node

 II.    The second largest element in a max-heap is always a child of the root node

III.    A max-heap can be constructed from a binary search tree in $ \mathrm\Theta(n) $ time

IV.    A binary search tree can be constructed from a max-heap in $ \mathrm\Theta(n) $ time

Which of the above statements are TRUE?

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7}exactly once is _____.

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), tthen what is the time complexity to re-fix the heap efficiently after the removal of the element?

A complete binary min-heap is made by including each integer in [1;1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________.

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

Array Index 1 2 3 4 5 6 7 8 9
Value 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

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number operations to convert the tree to a heap is

Consider the following array of elements
89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100
The minimum number of interchanges needed to convert it into a max-heap is

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 max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

Consider a binary max-heap implemented using an array.

Which one of the following array represents a binary max-heap?

Consider a binary max-heap implemented using an array.

What is the content of the array after two delete operations on the correct answer to the previous question?

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: