## Heap-Tree

 Question 1
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
 A 511
Data-Structures       Heap-Tree       GATE 2020
Question 1 Explanation:
The binary heap contains 1023 elements.
When it performs minimum comparisons it will take Ceil(n/2)
n=1023
= Ceil(1023/2)
= 512
So, the maximum element is also part of n/2. So, we have to subtract from the total elements
=512-1
=511
 Question 2
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.
 A 80 B 81 C 82 D 83
Data-Structures       Heap-Tree       Gate 2018
Question 2 Explanation:
--> We have 7 distinct integers {1,2,3,4,5,6,7} and sort it
--> After sorting, pick the minimum element and make it the root of the min heap.
--> So, there is only 1 way to make the root of the min heap.
--> Now we are left with 6 elements.
--> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80

Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .
 Question 3

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________.

 A 8 B 9 C 10 D 11
Data-Structures       Heap-Tree       GATE 2016 set-2
Question 3 Explanation: This is not possible because it violates a property of complete binary tree.
We have total [0, 1023] elements. It means that ∴ 20 + 21 + 22 + ⋯ + 2k = 1024
Add if 1(2(k+1)-1)/(2-1) [using formula for sum of k terms k+1 in G.P]
= 2(k+1) - 1 = 1024 - 1 = 1023
∴ The level ‘9’ at the depth of 8.
Actually we have 1023 elements, we can achieve a complete binary min heap of depth 9, which would cover all 1023 elements, but the max depth of node 9 can be only be 8.
 Question 4
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
 A Ω(logn) B Ω(n) C Ω(nlog n) D Ω(n2)
Data-Structures       Heap-Tree       GATE 2015 -(Set-2)
Question 4 Explanation:
Since left and right subtree is already a heap. So we can apply Heapify (node) which take log n time.
 Question 5
Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is
 A 4 B 5 C 2 D 3
Data-Structures       Heap-Tree       GATE 2015(Set-03)
Question 5 Explanation:
Let's first draw heap from the given array, → Swap 100 & 15 → Swap 100 & 50 → Swap 89 & 100 ∴ Total 3 interchanges are needed.
 Question 6
Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?
 A {25,12,16,13,10,8,14} B {25,14,13,16,10,8,12} C {25,14,16,13,10,8,12} D {25,14,12,13,10,8,16}
Data-Structures       Heap-Tree       2009
Question 6 Explanation:
Option-A: Violating a max heap property.
Option-B: Violating a max heap property.
Option-C: Question 7
Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on the correct answer to the previous question?
 A {14,13,12,10,8} B {14,12,13,8,10} C {14,13,8,12,10} D {14,13,12,8,10}
Data-Structures       Heap-Tree       2009
Question 7 Explanation:
Actual Graph: Step 1: Delete 25 Step 2: Step 3: Delete 16 Step 4: Step 5: ∴ Finary array elements: 14, 13, 12, 8, 10.
 Question 8
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
 A θ(log n) B θ(n) C θ(nlog n) D θ(n2)
Data-Structures       Heap-Tree       Gate-2008
Question 8 Explanation:
Inserting an element into binary(either max or min) heap takes O(logn) for all cases, but in question they clearly mentioned that n elements and inserting one by one n elements, so it takes 2n time. So, O(n).
Note: We can also insert all the elements once, there will be no difference on time complexity.
 Question 9
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
 A θ(log2n) B θ(log2log2n) C θ(n) D θ(nlog2n)
Data-Structures       Heap-Tree       Gate-2007
Question 9 Explanation:
Max heap is the complete binary tree that means each node has either zero children or two children except last level. So in worst case insertion of element is at last level. So, number of comparisons required at each level starting from root is equal to 1+2+4+8+16+---- this series is equal to "logn". All the elements are sorted, the binary search which will result in O(loglogn) number of comparisons.
 Question 10
In a binary max heap containing n numbers, the smallest element can be found in time
 A O(n) B O(log n) C O(log log n) D O(1)
Data-Structures       Heap-Tree       Gate-2006
Question 10 Explanation:
We have to search all the elements in max heap. So, the worst case time complexity for Max Heap is O(n).
 Question 11
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, nodes in the next level, from left to right, is stored from a to a. The nodes from the second level of the tree from left to right are stored from a 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?
 A 10, 7, 9, 8, 3, 1, 5, 2, 6, 4 B 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 C 10, 9, 4, 5, 7, 6, 8, 2, 1, 3 D 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Data-Structures       Heap-Tree       Gate-2006
Question 11 Explanation:   Question 12
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, nodes in the next level, from left to right, is stored from a to a. The nodes from the second level of the tree from left to right are stored from a 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?
 A 1, 3, 5, 6, 8, 9 B 9, 6, 3, 1, 8, 5 C 9, 3, 6, 8, 5, 1 D 9, 5, 6, 8, 3, 1
Data-Structures       Heap-Tree       Gate-2006
Question 12 Explanation: Question 13
Which of the following sequences of array elements forms a heap?
 A {23, 17, 14, 6, 13, 10, 1, 12, 7, 5} B {23, 17, 14, 6, 13, 10, 1, 5, 7, 12} C {23, 17, 14, 7, 13, 10, 1, 5, 6, 12} D {23, 17, 14, 7, 13, 10, 1, 12, 5, 7}
Data-Structures       Heap-Tree       Gate 2006-IT
Question 13 Explanation: In this every children and parent satisfies Max heap properties.
 Question 14
The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a MaxHeap. The resultant MaxHeap is
 A B C D Data-Structures       Heap-Tree       Gate-2004
Question 14 Explanation:
32, 15, 20, 30, 12, 25, 16       Question 15
In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time
 A Θ(n log n) B Θ(n) C Θ(log n) D Θ(1)
Data-Structures       Heap-Tree       Gate-2003
Question 15 Explanation:
The 7th smallest elements can be present in any of 7 levels. Then total possible elements can be present is seven levels is
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7th smallest element in Θ(1) time.
 Question 16
 A 0 B 1 C 2 D 3
Data-Structures       Heap-Tree       Gate-1996
Question 16 Explanation:
Lets draw first heap from given sequence,  Question 17
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≤n), the index of the parent is
 A B C D Data-Structures       Heap-Tree       Gate-2001
Question 17 Explanation:
Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1
There are 17 questions to complete.