Heap-Tree
Question 1 |
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.
80 | |
81 | |
82 | |
83 |
--> 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
Question 2 |
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
Ω(logn) | |
Ω(n) | |
Ω(nlog n) | |
Ω(n2) |
Question 3 |
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
4 | |
5 | |
2 | |
3 |
→ Swap 100 & 15
→ Swap 100 & 50
→ Swap 89 & 100
∴ Total 3 interchanges are needed.
Question 4 |
Consider a binary max-heap implemented using an array.
Which one of the following array represents a binary max-heap?
{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} |
Violating a max heap property.
Option-B:
Violating a max heap property.
Option-C:
Question 5 |
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 _________.
8 | |
9 | |
10 | |
11 |
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 6 |
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?
{14,13,12,10,8} | |
{14,12,13,8,10} | |
{14,13,8,12,10} | |
{14,13,12,8,10} |
Step 1: Delete 25
Step 2:
Step 3: Delete 16
Step 4:
Step 5:
∴ Binary array elements: 14, 13, 12, 8, 10.
Question 7 |
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) | |
θ(n2) |
Note: We can also insert all the elements once, there will be no difference on time complexity.
Question 8 |
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:
θ(log2n) | |
θ(log2log2n) | |
θ(n) | |
θ(nlog2n) |
Question 9 |
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) |
We have to search all the elements to reach the smallest element and heap using linear search.
To traverse all elements using linear search will take O(n) time.