This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Heap”.
1. If we implement heap as min-heap, deleting root node (value 1)from the heap. What would be the value of root node after second iteration if leaf node (value 100) is chosen to replace the root at start.
Explanation: The root is removed, and a node with the value 100 is used in its place. The fact that the root node must have a lower value than its children is a breach of property. As a result, the node with the value 100 will be shuffled with the node with the value 2. As a result, 2 becomes the nucleus. After all of the possible activities, it will stay at base. As a result, the root value would be 2.
2. If we implement heap as maximum heap , adding a new node of value 15 to the left most node of right subtree. What value will be at leaf nodes of the right subtree of the heap.
A) 15 and 1
B) 25 and 1
C) 3 and 1
D) 2 and 3
Explanation: There will be no breach since 15 is less than 25, and the node will stay in that location. As a result, leaf nodes with values of 15 and 1 will be found in the right subtree.
3. An array consists of n elements. We want to create a heap using the elements. The time complexity of building a heap will be in order of
D) O(n *logn *logn)
Explanation: The time it takes to add a single element to the heap would be N times the complexity. And because adding a single element takes logN time, N*logN is the answer.
4. In a max-heap, element with the greatest key is always in the which node?
A) Leaf node
B) First node of left sub tree
C) root node
D) First node of right sub tree
Explanation: One of the properties of max-heap is that the root node’s key must be greater than its children’s.
5. Heap exhibits the property of a binary tree?
Explanation: Since the leaf nodes are present at heights h or h-1, which is a property of a complete binary tree, the answer is yes.
6. What is the complexity of adding an element to the heap.
A) O(log n)
C) O(log n) & O(h)
Explanation: The total number of operations possible in relocating the current position to a new element is equal to the heap’s height.
7. The worst case complexity of deleting any arbitrary node value element from heap is __________
Explanation: The total number of operations possible in removing an existing node and relocating it to all of its associated nodes will be equal to the heap’s height.
8. Heap can be used as ________________
A) Priority queue
C) A decreasing order array
D) Normal Array
Explanation: Since the value of root must be greater or less than the value of both of its children, the heap behaves like a priority queue.
A heap is a data structure based on a tree in which all of the tree’s nodes are arranged in a certain order. If is the parent node of, then the value of follows a particular order with respect to the value of, and the same order will be followed in the tree.Heaps are used in many well-known algorithms, including Dijkstra’s algorithm for finding the shortest path, the heap sort sorting algorithm, and implementing priority queues. In essence, heaps are the data structure to use when you need to quickly access the maximum or minimum element.