Heap Data Structure MCQ
This section focuses on the "Heap" in Data Structure. These Multiple Choice Questions (MCQ) should be practiced to improve the Data Structure skills required for various interviews (campus interviews, walk-in interviews, company interviews), placements, entrance exams and other competitive examinations.
1. A ________ is a special Tree-based data structure in which the tree is a complete binary tree.?
Explanation: A Heap is a special Tree-based data structure in which the tree is a complete binary tree.
2. How many type of heap are there?
Explanation: There are 2 types of heap : max-heap and min-heap.
3.In which heap the root node must be greatest among the keys present at all of it’s children?
Explanation : Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children
4.What is the complexity of adding an element to the heap?
Explanation : The total possible operation in re locating the new location to a new element will be equal to height of the heap.
5. Heap can be used as ________________
Explanation : The property of heap that the value of root must be either greater or less than both of its children makes it work like a priority queue.
6. 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
Explanation: The total time taken will be N times the complexity of adding a single element to the heap. And adding a single element takes logN time, so That is equal to N*logN.
7. Min heap can be used to implement selection sort.
Explanation:In min heap, the insertion and deletion operation takes O(logn) time. Therefore, a selection sort with n insertions and n deletions can be implemented using a min heap in O(nlogn) operations.
8. Which one of the following array elements represents a binary min heap?
Explanation : A tree is min heap when data at every node in the tree is smaller than or equal to it’s children’ s data. So, only 8 10 12 25 14 17 generates required tree.
9. Given an array of element 5, 7, 9, 1, 3, 10, 8, 4. Which of the following is the correct sequences of elements after inserting all the elements in a min-heap?
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).
10. What is the amortized cost per operation of a skew heap?
Explanation : The amortized cost per operation of a skew heap is O(log N) since the worst case analysis of skew heap is O(N) and splay tree is O(M log N).