Min/Max Heap Multiple Choice Questions and Answers (MCQs)

Uncategorized

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Min/Max Heap”.

1. The ascending heap property is ___________
A) A[Parent(i)] =A[i]
B) A[Parent(i)] <= A[i]
C) A[Parent(i)] >= A[i]
D) A[Parent(i)] > 2 * A[i]

Explanation: The ascending heap is another name for the min heap. A min heap of size n is an almost complete binary tree with n nodes in which each node’s element is greater than or equal to its parent node’s element.

2. The procedure FindMin() to find the minimum element and the procedure DeleteMin() to delete the minimum element in min heap take _________
A) logarithmic and linear time constant respectively
B) constant and linear time respectively
C) constant and quadratic time respectively
D) constant and logarithmic time respectively

Explanation: The root is the highest node in the tree in the min heap. So, though finding it takes a constant amount of time, removing it takes a logarithmic amount of time. Since the root is replaced with the last element after it is deleted, and the process to preserve the min ordering is then activated.

3. Which one of the following array elements represents a binary min heap?
A) 12 10 8 25 14 17
B) 8 10 12 25 14 17
C) 25 17 14 12 10 8
D) 14 17 25 10 12 8

Explanation: When the data at each node in the tree is smaller than or equal to the data at its children’s nodes, the tree is called a min heap. As a result, only the numbers 8 10 12 25 14 17 generate the appropriate tree.

min-max-heap-questions-answers-q7

4. In a binary min heap containing n elements, the largest element can be found in __________ time.
A) O(n)
B) O(nlogn)
C) O(logn)
D) O(1)

Explanation: The smallest elements are at the root of the heap, while the largest are at the leaf nodes. To find the largest element, all leaf nodes must be verified. As a result, the worst-case time will be O. (n).

5. Min heap is a complete binary tree.
A) True
B) False

Explanation: The complete binary tree is a tree in which all stages, except probably the last, are entirely filled. The shape property of the min heap is preserved, making it a complete binary tree. The shape property ensures that all levels in the min heap are fully filled, except the last one, and fills the elements from left to right if the last level is not fully filled.

6. What will be the position of 5, when a max heap is constructed on the input elements 5, 70, 45, 7, 12, 15, 13, 65, 30, 25?
A) 5 will be at root
B) 5 will be at last level
C) 5 will be at second level
D) 5 can be anywhere in heap

Explanation: The largest element is at the top of the stack, and the smallest elements are at the bottom. It will be the last level since 5 is the smallest input variable.

7. The procedure given below is used to maintain min-order in the min heap. Find out the missing statements, represented as X.

procedure TrickleDownMin(i)
	 if A[i] has children then 
		m := index of smallest of the children 
		        or grandchildren (if any) of A[i] 
		if A[m] is a grandchild of A[i] then
			 if A[m] < A[i] then 
				swap A[i] and A[m]
				X: _______________________
					____________________
			 endif 	
			TrickleDownMin(m)
		 endif 
		else //{A[m] is a child of A[i]} 
			if A[m] < A[i] then 
				swap A[i] and A[m] 
		endif
	 endif

A) if A[m] > A[parent(m)] then
swap A[m] and A[parent(m)]

B) if A[m] > A[parent(m)] then
swap A[i] and A[parent(m)]
C) if A[m] < A[parent(m)] then
swap A[m] and A[parent(m)]
D) if A[m] > A[parent(m)] then
swap A[i] and A[parent(m)]

Explanation: We keep the min heap’s min-ordering in the TrickleDownMin() procedure. In this procedure, we find the element’s lowest child or grandchild at positions i. We verify that the lowest element is smaller than both its parent and A[i] if it is grandchild.

8. Descending priority queue can be implemented using ______
A) max heap
B) min heap
C) min-max heap
D) trie

Explanation: The elements in a descending priority queue are arranged according to their priority or importance, and they can be removed in that order. As a result, max heap can be used to effectively execute it.

9. Min heap can be used to implement selection sort.
A) True
B) False

Explanation: The insertion and deletion operations in the min heap take O(logn) time. As a result, a selection sort of n insertions and n deletions can be implemented in O(nlogn) operations using a min heap.

10. Which of the following is the valid min heap?

A)

min-max-heap-questions-answers-q3a

B)

min-max-heap-questions-answers-q3b

C)

min-max-heap-questions-answers-q3c

D)

min-max-heap-questions-answers-q3d


Explanation: The smallest elements are at the root of the heap, while the largest are at the leaf nodes. To find the largest element, all leaf nodes must be verified.

The min-max heap is a total binary tree data structure that incorporates the advantages of both a min-heap and a max-heap, namely, constant time retrieval and logarithmic time removal of both the minimum and maximum elements. As a result, the min-max heap is an excellent option for implementing a double-ended priority queue. Min-max heaps, including binary min- and max-heaps, allow logarithmic insertion and deletion and can be constructed in linear time. Min-max heaps are often implicitly expressed in an array, thus the term “implicit data structure.”

Leave a Reply

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