## 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.

--> 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 2 |

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

∴ 2

^{0}+ 2

^{1}+ 2

^{2}+ ⋯ + 2

^{k}= 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 3 |

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) | |

Ω(n ^{2}) |

*log n*time.

Question 4 |

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 5 |

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 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) | |

θ(n ^{2}) |

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:

θ(log _{2}n) | |

θ(log _{2}log_{2}n) | |

θ(n) | |

θ(nlog _{2}n) |

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.

Question 10 |

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?

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 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[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, Q.76. 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 12 |

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is

Question 13 |

In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

Θ(n log n) | |

Θ(n) | |

Θ(log n) | |

Θ(1) |

^{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.

Question 14 |

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

i-1 | |

⌊i/2⌋ | |

⌈i/2⌉ | |

(i+1)/2 |

Left Child is at index: 2i

Right child is at index: 2*i+1

Question 15 |

The minimum number of interchanges needed to convert the array

89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70

into a heap with the maximum element at the root is

0 | |

1 | |

2 | |

3 |

Question 16 |

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 _______.

511 |

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 17 |

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} |

In this every children and parent satisfies Max heap properties.

Question 18 |

Consider the array A = 〈4, 1, 3, 2, 16, 9, 10, 14, 8, 7〉. After building heap from the array A, the depth of the heap and the right child of max-heap are and respectively. (Root is at level 0).

3, 14 | |

3, 10 | |

4, 14 | |

4, 10 |

Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max-heapify operation from the largest index parent node (node having 1 or more children).

The above Heap is the max-heap where each root node have maximum value.

Now depth of the Max-heap is 3 and right child of the Root node is 10.

Question 19 |

O(logn) | |

O(n) | |

O(nlogn) | |

O(n ^{2} ) |

Possibility-2: If you inserted one after the other then time complexity will be O(nlogn). For one insertion it will take O(logn) because need to apply maxHeapify. For n elements it will be O(nlogn)

Note: We can also insert all the elements once, there will be no difference on time complexity.

But according GATE solution they given possibility-1.

Question 20 |

O(log _{2} n) | |

O(nlog _{2} n) | |

O(n) |

Note: If you apply linear search it will take O(logn) and binary search it will take O(loglogn). If you want to insert an element into already created heap is O(logn) because you need to apply

**maxheapify.**

Question 21 |

The elements 42, 25, 30, 40, 22, 35, 26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array implementation as

<42, 35, 40, 22, 25, 26, 30> | |

<42, 35, 40, 22, 25, 30, 26>
| |

<42, 40, 35, 25, 22, 26, 30>
| |

<42, 40, 35, 25, 22, 30, 26> |

The resultant MAX_Heap will look like

<42, 40, 35, 25, 22, 30, 26>

Question 22 |

O(n) | |

O(logn) | |

O(loglogn) | |

O(A) |

Question 23 |

Those that support recursion | |

Those that use dynamic scoping | |

Those that use global variables | |

Those that allow dynamic data structures |

→ So the languages which allow dynamic data structure require heap allocation at runtime.

Question 24 |

A | |

B | |

C | |

D |

Option B is satisfied max heap property.

Option C is violated max heap property because 7 is greater than his root.

Option D is violated max heap property because 9,10,8,7 elements are greater than his root.

Question 25 |

<42, 35, 40, 22, 25, 26, 30> | |

<42, 35, 40, 22, 25, 30, 26> | |

<42, 40, 35, 25, 22, 26, 30> | |

<42, 40, 35, 25, 22, 30, 26> |

The resultant MAX_Heap will look like

< 4 2, 40, 35, 25, 22, 30, 26 >

Question 26 |

3, 14 | |

3, 10 | |

4, 14 | |

4, 10 |

Step 1: Since a heap is a almost complete binary tree so build a heap first.

Step 2: Since the above heap is not a max heap so to convert a heap into max-heap start applying max- heapify operation from the largest index parent node(node having 1 or more children).

The above Heap is the max-heap where each root node have maximum value. Now depth of the Max-heap is 3 and right child of the Root node is 10.

Question 27 |

θ(n) and θ(1) respectively | |

θ(n) and θ(n) respectively | |

θ(1) and θ(1) respectively | |

None of the above |

Question 28 |

O(log n) | |

O(n) | |

O(n logn) | |

O(n ^{2}) |

// Input: A: an (unsorted) array

// Output: A modified to represent a heap.

//

**Running Time: O(n) where n = length[A]**

1 heap-size[A] ← length[A]

2 for i ← Floor(length[A]/2) downto 1

3 Max-Heapify(A, i)

The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.

→ Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.

Question 29 |

O(1) | |

O(lgn) | |

O(n) | |

O(nlgn) |

Build-Max-Heap(A)

// Input: A: an (unsorted) array

// Output: A modified to represent a heap.

**// Running Time: O(n) where n = length[A]**

1 heap-size[A] ← length[A]

2 for i ← Floor(length[A]/2) downto 1

3 Max-Heapify(A, i)

The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner. It is based on the observation that the array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ..., n are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.

→ Build-Max-Heap runs Max-Heapify on each of the remaining tree nodes.

Question 30 |

maximum | |

minimum | |

sum | |

product | |

None of the above |

In Max heap→ The root element is greater than of his all childs.

In Min heap→ Te root element is smaller than of his all childs.

Question 31 |

a queue | |

a heap | |

a stack | |

a binary search tree |

Question 32 |

20, 18, 17, 15, 13, 12, 10 | |

20, 18, 17, 12, 13, 10, 15 | |

20, 18, 17, 10, 12, 13, 15 | |

20, 18, 17, 13, 12, 10, 15 |

Question 33 |

h | |

z ^{h} | |

⌈n/(z ^{h} )⌉ | |

⌈n/z ^{ h+1 )} | |

None of the above |

Question 34 |

19 | |

68 | |

48 | |

32 |

Question 35 |

A min-max heap is defined as follows: Each node at an even level in the tree is less than all of its descendants, while each node at an odd Level in the tree is greater than all of its descendents

If the values are inserted in the order (3,6,9,19,27,48,50,66) in the min-max heap, what value would be found at position 5 in min-max heap (root is counted as position 1)

6 | |

27 | |

48 | |

50 | |

None of the above |

Question 36 |

O(nlog n) | |

O(log n) | |

O(n^2) | |

O(n) |

Question 37 |

O(n) | |

O(log _{2} n) | |

O(1) | |

O(log _{2} log_{2} n) |

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.