HeapTree
Question 1 
Consider the array representation of a binary minheap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
511 
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
=5121
=511
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
=5121
=511
Question 2 
The number of possible minheaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.
80  
81  
82  
83 
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 .
> 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 minheap 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 _________.
8  
9  
10  
11 
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
∴ 2^{0} + 2^{1} + 2^{2} + ⋯ + 2^{k} = 1024
Add if 1(2^{(k+1)}1)/(21) [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 maxheaps. The lower bound for the number of operations to convert the tree to a heap is
Ω(logn)  
Ω(n)  
Ω(nlog n)  
Ω(n^{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 maxheap is
4  
5  
2  
3 
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.
→ Swap 100 & 15
→ Swap 100 & 50
→ Swap 89 & 100
∴ Total 3 interchanges are needed.
Question 6 
Consider a binary maxheap implemented using an array.
Which one of the following array represents a binary maxheap?
{25,12,16,13,10,8,14}  
{25,14,13,16,10,8,12}  
{25,14,16,13,10,8,12}  
{25,14,12,13,10,8,16} 
Question 6 Explanation:
OptionA:
Violating a max heap property.
OptionB:
Violating a max heap property.
OptionC:
Violating a max heap property.
OptionB:
Violating a max heap property.
OptionC:
Question 7 
Consider a binary maxheap implemented using an array.
What is the content of the array after two delete operations on the correct answer to the previous question?
{14,13,12,10,8}  
{14,12,13,8,10}  
{14,13,8,12,10}  
{14,13,12,8,10}

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.
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
θ(log n)  
θ(n)  
θ(nlog n)
 
θ(n^{2})

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.
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:
θ(log_{2}n)  
θ(log_{2}log_{2}n)  
θ(n)  
θ(nlog_{2}n)

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
O(n)  
O(log n)  
O(log log n)
 
O(1) 
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 3ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3ary 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 3ary 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?
10, 7, 9, 8, 3, 1, 5, 2, 6, 4  
10, 9, 8, 7, 6, 5, 4, 3, 2, 1
 
10, 9, 4, 5, 7, 6, 8, 2, 1, 3
 
10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Question 11 Explanation:
Question 12 
A 3ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3ary 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 3ary 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 3ary max heap?
1, 3, 5, 6, 8, 9
 
9, 6, 3, 1, 8, 5
 
9, 3, 6, 8, 5, 1
 
9, 5, 6, 8, 3, 1

Question 12 Explanation:
Question 13 
Which of the following sequences of array elements forms a heap?
{23, 17, 14, 6, 13, 10, 1, 12, 7, 5}  
{23, 17, 14, 6, 13, 10, 1, 5, 7, 12}  
{23, 17, 14, 7, 13, 10, 1, 5, 6, 12}  
{23, 17, 14, 7, 13, 10, 1, 12, 5, 7} 
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
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 7^{th} smallest element can be found in time
Θ(n log n)
 
Θ(n)  
Θ(log n)
 
Θ(1)

Question 15 Explanation:
The 7^{th} 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 7^{th} smallest element in Θ(1) time.
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7^{th} smallest element in Θ(1) time.
Question 16 
0  
1  
2  
3 
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
Question 17 Explanation:
Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1
Left Child is at index: 2i
Right child is at index: 2*i+1
There are 17 questions to complete.