Heap Tree


Question 1
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?
A
Both Extract-Max(A) and Insert(A,key) run in O(1).
B
Both Extract-Max(A) and Insert(A,key) run in O(log(n)).
C
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n).
D
Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)).
GATE CSE 2023   Data Structure
Question 2
Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap?
A
23, 17, 10, 6, 13, 14, 1, 5, 7, 12
B
23, 17, 14, 7, 13, 10, 1, 5, 6, 12
C
23, 17, 14, 6, 13, 10, 1, 5, 7, 15
D
23, 14, 17, 1, 10, 13, 16, 12, 7, 5
GATE CSE 2023   Data Structure


Question 3
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 4
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 5
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


There are 5 questions to complete.

1 thought on “Heap Tree”

Leave a Comment