Heap Tree
Q21.
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?Q22.
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements '1' and '7' are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:Q23.
In a binary max heap containing n numbers, the smallest element can be found in timeQ24.
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node \left \lfloor (n - 1) /2 \right \rfloor, and doing this adjustment up to the root node (root node is at index 0) in the order \left \lfloor (n - 1) /2 \right \rfloor,\left \lfloor (n - 3) /2 \right \rfloor, ....., 0. The time required to construct a heap in this manner isQ25.
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3-ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?Q26.
In a heap with n elements with the smallest element at the root, the 7^{th} smallest element ban be found in timeQ27.
The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a MaxHeap. The resultant MaxHeap isQ28.
The minimum number of interchanges needed to convert the array into a max-heap is 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70Q29.
A data structure is required for storing a set of integers such that each of the following operations can be done in O(logn) time, where n is the number of elements in the set. 1. Delection of the smallest element. 2. Insertion of an element if it is not already present in the set. Which of the following data structures can be used for this purpose ?Q30.
Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i\leq n ) , the index of the parent is