/* */ Click to Join Live Class with Shankar sir Call 9798158723

# Heap Data Structure MCQ

Q1.What is the location of parent node for any arbitary node i?
1. (i/2) position
2. (i+1)/ position
3. floor(i/2) position
4. ceil(i/2) position

Explanations :For any node child nodes are located at either 2*i , 2*i +1 So the parent node could be found by taking the floor of the half of child node.
Q2.State the complexity of algorithm given below
```int function(vector arr)

int len=arr.length();

if(len==0)

return;

temp=arr[len-1];

arr.pop_back();

return temp;```
1. o(n)
2. O(logn)
3. O(1)
4. O(n logn)

Explanations :Deletion in a min-heap is in O(1) time.
Q3.Time taken in decreasing the node value in a binomial heap is
1. O(n)
2. O(1)
3. O(logn)
4. O(nlogn)

Explanations :Decreasing a node value may result in violating the min property. As a result be there would be exchange in the value of parent and child which at max goes up to height of the heap.
Q4.What does this pseudo_code return ?
```int myfun(heap_arr[])

{

int mini=INF;

for(int i=0;i

mini=min(mini,heap_arr)

return mini;

}```
1. Last added element to heap
2. First element added to heap
3. Root of the heap
4. Leftmost node of the heap

Explanations :The function return minimum value in the heap_Array which is equal to the root value of the heap.
Q5.Heap can be used as¦
1. Priority queue
2. Stack
3. A decreasing order array
4. None of the mentioned

Explanations :The property of heap that the value of root must be either greater or less than both of its children makes it work like a priority queue.
Q6. Does there exist a heap with seven distinct elements so that the In order traversal gives the element in sorted order.
1. Yes
2. No
3. Both 1and2
4. None of these

Explanations :No, The inorder traversal will not give elements in sorted order. As heap is implemented as either min-heap or max-heap ,the root will be have highest or lowest value than remaining values of the nodes .So this traversal will not give a sorted list.
Q7. What is wrong with the following code of insertion in fibonacci heap. Choose the correct option
```FIB-INSERT(H, x)

degree[x]= 0

p[x]=  NIL

child[x] =NIL

left[x] =x

right[x] =x

mark[x] =FALSE

concatenate the root list containing x with root list H

if min[H] = NIL or key[x] > key[min[H]]

then min[H]= x

n[H]= n[H] + 1```
1. Line -11
2. Line -3
3. Line -9
4. Line -7

Explanations :The main characteristics of a Fibonacci heap is violated since min[H] must contain one with smallest value.
Q8. What will be the order of new heap created after union of heap H1 and H2 when created by the following code.Initially both are of the order n.
```FIB_UNION(H1,H2)

{

H =MAKE_HEAP()

min[H]= min[H1]

concatenate the root list of H2 with the root list of H

if (min[H1] = NIL) or (min[H2]!= NIL and min[H2] < min[H1])

then min[H] = min[H2]

n[H]=  n[H1] + n[H2]

free the objects H1 and H2

return H

}```
1. n+1
2. n+n/2
3. nlogn
4. 2*n

Explanations :Union of two trees increase the order of the resultant by atmost value 1.
Q9.What is the complexity of adding an element to the heap.
1. O(log n)
2. O(h)
3. O(log n) & O(h)
4. None of the mentioned