Heaps are specialized tree-based data structures that have a variety of applications, especially in algorithms for finding the shortest path like Dijkstra’s. They can be visualized as binary trees but must satisfy the heap property. Dive into this MCQ set to test your knowledge about heaps!
1. Which of the following properties must be maintained in a Min-Heap?
Answer:
Explanation:
In a Min-Heap, for any given node I, the value of I is always less than or equal to its children.
2. Which operation has a time complexity of O(1) in a binary heap?
Answer:
Explanation:
In a Min-Heap, the root always contains the smallest element, and it can be retrieved in O(1) time.
3. What is the maximum number of children a node can have in a binary heap?
Answer:
Explanation:
A binary heap is a binary tree; hence, each node can have a maximum of 2 children.
4. In a Max-Heap:
Answer:
Explanation:
In a Max-Heap, for any given node I, the value of I is always greater than or equal to its children.
5. Which of the following is NOT a valid application of heap?
Answer:
Explanation:
Infix to postfix conversion is typically done using a stack. Heaps are not used for this purpose.
6. If the parent node is at index ‘I’ in a 0-indexed binary heap, where can you find its left child?
Answer:
Explanation:
For a 0-indexed binary heap, the left child is found at 2I + 1.
7. Which of the following is true about a binary heap?
Answer:
Explanation:
A binary heap is always a complete binary tree, meaning every level of the tree is fully filled except possibly the last level, which is filled from left to right.
8. Which data structure is typically used to implement a heap?
Answer:
Explanation:
Heaps are usually implemented using arrays because of their complete binary tree property, which allows easy access to parent and child nodes.
9. In a Min-Heap with elements: 1, 3, 5, 7, 9, 2, 4. Which one is the root?
Answer:
Explanation:
In a Min-Heap, the root always contains the smallest element.
10. If the parent node is at index ‘I’ in a 1-indexed binary heap, where can you find its right child?
Answer:
Explanation:
For a 1-indexed binary heap, the right child is found at 2I + 1.
11. Heapify operation is used to:
Answer:
Explanation:
Heapify operation is used to reorganize the heap after insertion or removal of an element to ensure the heap property is maintained.
12. Which of these sorting algorithms uses a binary heap?
Answer:
Explanation:
Heap sort utilizes a binary heap (either Max-Heap or Min-Heap) to sort elements.
13. Deleting the maximum element from a Max-Heap has a time complexity of:
Answer:
Explanation:
Deleting the maximum element requires removing the root and then reorganizing the heap using heapify, which takes O(log n) time.
14. Which of the following algorithms can be optimized using a Min-Heap?
Answer:
Explanation:
Dijkstra’s algorithm can be optimized using a Min-Heap to efficiently select the next node with the shortest distance.
15. In a Max-Heap, the maximum element can be found in:
Answer:
Explanation:
In a Max-Heap, the maximum element is always found at the root.
Heaps are crucial when it comes to algorithms that require efficient maximum or minimum element look-up, insertion, and deletion. It’s essential to understand their properties and the difference between their types. Keep refining your understanding, and you’ll see how these structures play an essential role in various real-world applications!