Data Structure Questions and Answers – Binary Heap

«
»

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses 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)
View Answer

Answer: b
Explanation: The space complexity of searching an element in heap is O (n). Heap consists of n elements and we need to compare every element. Here no addition or deletion of elements takes place. Hence space complexity is O (n).
advertisement

2. What is the best case complexity in building a heap?
a) O(nlogn)
b) O(n2)
c) O(n*longn *logn)
d) O(n)
View Answer

Answer: d
Explanation: The best case complexity occurs in bottom-up construction when we have a sortes array given.

3. Given the code, choose the correct option that is consistent with the code. (Here A is the heap)

advertisement
advertisement
	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)

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) It is used to search element in any heap
View Answer

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.
advertisement

4. What is the location of a 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
View Answer

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 given below.

advertisement
	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)
View Answer

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

6. Given an array of element 5, 7, 9, 1, 3, 10, 8, 4. Which of the following are the correct sequences of elements after inserting all the elements in a min-heap?
a) 1,3,4,5,7,8,9,10
b) 1,4,3,9,8,5,7,10
c) 1,3,4,5,8,7,9,10
d) 1,3,7,4,8,5,9,10
View Answer

Answer: a
Explanation: Building a min-heap the result will a sorted array so the 1, 3, 4, 5, 7, 8, 9, 10 is correct. If we change the implementation strategy 1, 4, 3, 8, 9, 5, 7, 10 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.

1. add(int k)
2. {
3.     heap_size++;
4.     int i = heap_size - 1;
5.     harr[i] = k;
6.     while (i != 0 && harr[parent(i)] < harr[i])
7.     {
8.             swap(&harr[i], &harr[parent(i)]);
9.             i = parent(i);
10.    }
11. }

a) Line – 3
b) Line – 5
c) Line – 6
d) Line – 7
View Answer

Answer: c
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.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter