Data Structure Questions and Answers – Binary Heap

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Binary Heap”.

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

Explanation: Child nodes are located at either 2i or 2i +1 for any node. As a result, the parent node can be identified by taking half of the child node’s floor.

2. State the complexity of algorithm given 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)

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

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

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

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

Explanation: For a (min) binary heap, the state under while is incorrect. While(i!=0 && harr[parent(i)] > harr[i]) is the right state. Otherwise, the heap would be constructed as a max-binary heap.

5. What is the space complexity of searching in a heap?
A) O(logn)
B) O(n)
C) O(1)
D) O(nlogn)

Explanation: The quest for an element in a heap has an O space complexity (n). We need to compare each element in a heap of n elements. There is no element addition or deletion here. As a result, the space complexity is O. (n).

6. What is the best case complexity in building a heap?
A) O(nlogn)
B) O(n2)
C) O(n*longn *logn)
D) O(n)

Explanation: When we have a sortes series, the best case complexity exists in bottom-up construction.

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

	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

Explanation: Since we are comparing the current value to the parent of that node in each condition. So this is the Max heap’s construct feature.

The binary heap is a data structure that resembles a binary tree. Priority queues are often implemented using binary heaps: 162–163 words J. W. J. Williams implemented the binary heap as a data structure for heapsort in 1964. A binary heap is a binary tree with the following two constraints: A binary heap is a complete binary tree; that is, all levels of the tree, except probably the last (deepest), are entirely filled, and the nodes of that level are filled from left to right if the last level of the tree is not complete.

Leave a Reply

Your email address will not be published. Required fields are marked *