Data Structures Multiple Choice Questions and Answers on Binary Heap

1. What is the space complexity of searching in a heap?

a) O(logn)
b) O(n)
c) O(1)
d) O(nlogn)

Answer: b

Explanation: None.

2. What is the best case complexity in builading a heap?

a) O(nlogn)
b) O(n2)
c) O(n*longn *logn)
d) O(n)

Answer: d

Explanation: The best case compexity occur in botton-up construction when we have a sortes array given.

3. Given the code ,choose the correct option that is consistent with the code

 build(A,i)
 left-> 2*i
 right->2*i +1
 temp- > i
 if(left<= heap_length[A] ans A[left] >A[temp])
 temp -> left
 if (right = heap_length[A] and A[right] > A[temp])
 temp->right
 if temp!= i
 swap(A[i],A[temp])
 build(A,temp)

Here A is the heap

a) It is the build function of max heap.
b) It is the build function of min heap.
c) It is general build function of any heap.
d) None of the mentioned

Answer: a

Explanation: Since in every condition we are comparing the current value is less than the parent of that node.So this is build function of Max heap.

4. What is the location of parent node for any arbitary node i?

a) (i/2) position
b) (i+1)/ position
c) floor(i/2) position
d) ceil(i/2) position

Answer: c

Explanation: 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.

5. State the complexity of algorithm gien below

 int function(vector<int> arr)
 int len=arr.length();
 if(len==0)
 return;
 temp=arr[len-1];
 arr.pop_back();
 return temp;

a) o(n)
b) O(logn)
c) O(1)
d) O(n logn)

Answer: c

Explanation: Deletion in a min-heap is in O(1) time.

6. Given an array of element 5,7,9,1,3,10,8,4. Tick all the correct sequences of elements after inserting all the elements in a min-heap.

a) 1,3,4,7,8,9,10
b) 1,4,3,8,9,5,7,10
c) 1,3,4,5,8,7,9,10
d) None of these

Answer: a

Explanation: Building a min-heap the result will a sorted array so the option a is correct .If we change the implementation strategy option- b is also correct. (First filling the right child rather than left child first).

7. For construction of a binary heap with property that parent node has value less than child node.In reference to that which line is incorrect. Line indexed from 1.

add(int k)
{
 heap_size++;
     int i = heap_size - 1;
     harr[i] = k;
     while (i != 0 && harr[parent(i)] < harr[i])
     {
         swap(&harr[i], &harr[parent(i)]);
         i = parent(i);
        }
}

a) Line -3
b) Line – 5
c) Line – 6
d) Line -7

Answer: b

Explanation: The condition under while condition is wrong for a (min) binary heap The correct condition should be while(i!=0 && harr[parent(i)] > harr[i]). Otherwise the constructed heap will be a max-binary heap.