Heap-Tree

Question 1

Consider the array A = 〈4, 1, 3, 2, 16, 9, 10, 14, 8, 7〉. After building heap from the array A, the depth of the heap and the right child of max-heap are and respectively. (Root is at level 0).

A
3, 14
B
3, 10
C
4, 14
D
4, 10
       Data-Structures       Heap-Tree       UGC-NET JUNE Paper-2
Question 1 Explanation: 
A heap is a MAX-Heap if all the root nodes (parent nodes) have maximum value.
Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max-heapify operation from the largest index parent node (node having 1 or more children).






The above Heap is the max-heap where each root node have maximum value.
Now depth of the Max-heap is 3 and right child of the Root node is 10.
Question 2
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. Total time required for this is
A
O(logn)
B
O(n)
C
O(nlogn)
D
O(n​ 2​ )
       Data-Structures       Heap-Tree       Nielit Scientist-C 2016 march
Question 2 Explanation: 
Possibility-1: Inserting an element into binary(either max or min) heap takes O(logn) for all cases, but in question they clearly mentioned that n elements. O(n) complexity can be to take the ‘n’ elements of the heap and other ‘n’ elements together and construct heap So, O(n).
Possibility-2: If you inserted one after the other then time complexity will be O(nlogn). For one insertion it will take O(logn) because need to apply maxHeapify. For n elements it will be O(nlogn)
Note: We can also insert all the elements once, there will be no difference on time complexity.
But according GATE solution they given possibility-1.
Question 3
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 position for the newly inserted element, the number of comparisons performed is
A
O(log​ 2​ n)
B
O(nlog​ 2​ n)
C
O(n)
       Data-Structures       Heap-Tree       Nielit Scientist-C 2016 march
Question 3 Explanation: 
Max heap is the complete binary tree that means each node has either zero children or two children except last level. So in worst case insertion of element is at last level. So, number of comparisons required at each level starting from root is equal to 1+2+4+8+16+---- this series is equal to "logn".
Note: If you apply linear search it will take O(logn) and binary search it will take O(loglogn). If you want to insert an element into already created heap is O(logn) because you need to apply maxheapify.
Question 4

The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as

A
<42, 35, 40, 22, 25, 26, 30>
B
<42, 35, 40, 22, 25, 30, 26>
C
<42, 40, 35, 25, 22, 26, 30>
D
<42, 40, 35, 25, 22, 30, 26>
       Data-Structures       Heap-Tree       UGC-NET DEC Paper-2
Question 4 Explanation: 
After inserting each element we will apply MAX-Heapify operation to get the MAX-Heap.
The resultant MAX_Heap will look like

<42, 40, 35, 25, 22, 30, 26>
Question 5
In a binary max heap containing n numbers, the smallest element can be found in time
A
O(n)
B
O(logn)
C
O(loglogn)
D
O(A)
       Data-Structures       Heap-Tree       NieLit STA 2016 March 2016
Question 5 Explanation: 
In Binary Max Heap, the smallest element will always be a leaf node either in left subtree or right subtree. So you have to traverse both left and right subtrees in each step to find the smallest element. So, it takes O(n) time.
Question 6
Which of the following is a valid heap ?
A
A
B
B
C
C
D
D
       Data-Structures       Heap-Tree       UGC NET CS 2017 Jan -paper-2
Question 6 Explanation: 
Option A is violated max heap property because 8 is greater than his root.
Option B is satisfied max heap property.
Option C is violated max heap property because 7 is greater than his root.
Option D is violated max heap property because 9,10,8,7 elements are greater than his root.
Question 7
The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as
A
<42, 35, 40, 22, 25, 26, 30>
B
<42, 35, 40, 22, 25, 30, 26>
C
<42, 40, 35, 25, 22, 26, 30>
D
<42, 40, 35, 25, 22, 30, 26>
       Data-Structures       Heap-Tree       UGC NET CS 2018-DEC Paper-2
Question 7 Explanation: 
After inserting each element we will apply MAX-Heapify operation to get the MAX-Heap.
The resultant MAX_Heap will look like

< 4 2, 40, 35, 25, 22, 30, 26 >
Question 8
Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are__________ and __________ respectively. (Root is at level 0).
A
3, 14
B
3, 10
C
4, 14
D
4, 10
       Data-Structures       Heap-Tree       UGC NET CS 2018 JUNE Paper-2
Question 8 Explanation: 
A heap is a MAX-Heap if all the root nodes(parent nodes) have maximum value.
Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max- heapify operation from the largest index parent node(node having 1 or more children).



The above Heap is the max-heap where each root node have maximum value. Now depth of the Max-heap is 3 and right child of the Root node is 10.
Question 9
When the priority queue is represented by max heap, the insertion and deletion of an element can be performed in (queue containing n elements)
A
θ(n) and θ(1) respectively
B
θ(n) and θ(n) respectively
C
θ(1) and θ(1) respectively
D
None of the above
       Data-Structures       Heap-Tree       UGC NET CS 2011 June-Paper-2
Question 9 Explanation: 

Question 10
The time complexity to build a heap with a list of n numbers is
A
O(log n)
B
O(n)
C
O(n logn)
D
O(n2)
       Data-Structures       Heap-Tree       UGC NET CS 2013 June-paper-2
Question 10 Explanation: 
Build-Max-Heap(A)
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heap-size[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 Max-Heapify(A, i)
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.
→ Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.
Question 11
The time complexity to build a heap of n elements is
A
O(1)
B
O(lgn)
C
O(n)
D
O(nlgn)
       Data-Structures       Heap-Tree       UGC NET CS 2010 Dec-Paper-2
Question 11 Explanation: 
The time complexity to build a heap of n elements is O(n).
Build-Max-Heap(A)
// Input: A: an (unsorted) array
// Output: A modified to represent a heap.
// Running Time: O(n) where n = length[A]
1 heap-size[A] ← length[A]
2 for i ← Floor(length[A]/2) downto 1
3 Max-Heapify(A, i)
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.
→ Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.
Question 12
In a heap, every element is __________ of all the elements in the subtree.
A
maximum
B
minimum
C
sum
D
product
E
None of the above
       Data-Structures       Heap-Tree       UGC NET CS 2008 Dec-Paper-2
Question 12 Explanation: 
Heap is complete binary tree. Sometimes we are calling as binary heap that may be either Max heap or Min heap.
In Max heap→ The root element is greater than of his all childs.
In Min heap→ Te root element is smaller than of his all childs.
Question 13
A priority queue is implemented as a max-heap. Initially, it has ve elements. The level-order traversal of the heap is as follows:  20, 18, 15, 13, 12  Two new elements ‘10’ and ‘17’are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is:
A
20, 18, 17, 15, 13, 12, 10
B
20, 18, 17, 12, 13, 10, 15
C
20, 18, 17, 10, 12, 13, 15
D
20, 18, 17, 13, 12, 10, 15
       Data-Structures       Heap-Tree       UGC NET CS 2016 Aug- paper-3
Question 13 Explanation: 


There are 13 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com