Heap Tree

Question 1
Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?
A
\Theta (1)
B
\Theta (\log n)
C
\Theta ( n)
D
\Theta (n \log n)
GATE CSE 2021 SET-2   Data Structure
Question 2
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 ___________.
A
512
B
511
C
1022
D
10
GATE CSE 2020   Data Structure
Question 3
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 \Theta (n) time.
IV. A binary search tree can be constructed from a max-heap in \Theta (n) time.

Which of the above statements is/are TRUE?
A
I, II and III
B
I, II and IV
C
I, III and IV
D
II, III and IV
GATE CSE 2019   Data Structure
Question 4
Given a binary-max heap. The elements are stored in an arrays as 25,14,16,13,10,8,12. What is the content of the array after two delete operations?
A
14,13,8,12,10
B
14,12,13,10,8
C
14,13,12,8,10
D
14,13,12,10,8
ISRO CSE 2018   Data Structure
Question 5
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _____.
A
7
B
16
C
240
D
80
GATE CSE 2018   Data Structure
Question 6
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_____. .
A
9
B
8
C
1022
D
1021
GATE CSE 2016 SET-2   Data Structure
Question 7
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 thearray.If the heap tree has depth d (number of edges on the path from the root to the farthest leaf),the n what is the time complexity to re-fix the heap efficiently after the removal of the element?
A
O(1)
B
O(d) but not O(1)
C
O(2^{d}) but not O(d)
D
O(d 2^{d}) but not O(2^{d})
GATE CSE 2016 SET-1   Data Structure
Question 8
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
4
B
5
C
2
D
3
GATE CSE 2015 SET-3   Data Structure
Question 9
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
A
\Omega (log n)
B
(n)
C
\Omega (n \; log n)
D
\Omega (n^{2})
GATE CSE 2015 SET-2   Data Structure
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
GATE CSE 2015 SET-1   Data Structure
There are 10 questions to complete.

1 thought on “Heap Tree”

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.