## Heap-Tree

Question 1 |

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 |

Question 1 Explanation:

A heap is a MAX-Heap if all the root nodes (parent nodes) have maximum value.

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.

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

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. Total time required for this is

O(logn) | |

O(n) | |

O(nlogn) | |

O(n ^{2} ) |

Question 2 Explanation:

Possibility-1: 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. O(n) complexity can be to take
the ‘n’ elements of the heap and other ‘n’ elements together and construct heap So, O(n).

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.

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

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 position for the newly inserted element, the number of comparisons performed is

O(log _{2} n) | |

O(nlog _{2} n) | |

O(n) |

Question 3 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".

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

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

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

Question 4 Explanation:

After inserting each element we will apply MAX-Heapify operation to get the MAX-Heap.

The resultant MAX_Heap will look like

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

The resultant MAX_Heap will look like

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

Question 5 |

In a binary max heap containing n numbers, the smallest element can be found in time

O(n) | |

O(logn) | |

O(loglogn) | |

O(A) |

Question 5 Explanation:

In Binary Max Heap, the smallest element will always be a leaf node either in left subtree or right subtree. So you have to traverse both left and right subtrees in each step to find the smallest element. So, it takes O(n) time.

Question 6 |

Which of the following is a valid heap ?

A | |

B | |

C | |

D |

Question 6 Explanation:

Option A is violated max heap property because 8 is greater than his root.

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.

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

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

Question 7 Explanation:

After inserting each element we will apply MAX-Heapify operation to get the MAX-Heap.

The resultant MAX_Heap will look like

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

The resultant MAX_Heap will look like

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

Question 8 |

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 |

Question 8 Explanation:

A heap is a MAX-Heap if all the root nodes(parent nodes) have maximum value.

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.

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

When the priority queue is represented by max heap, the insertion and deletion of an element can be performed in (queue containing n elements)

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

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

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

None of the above |

Question 9 Explanation:

Question 10 |

The time complexity to build a heap with a list of n numbers is

O(log n) | |

O(n) | |

O(n logn) | |

O(n ^{2}) |

Question 10 Explanation:

Build-Max-Heap(A)

// Input: A: an (unsorted) array

// Output: A modified to represent a heap.

//

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.

// 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 11 |

The time complexity to build a heap of n elements is

O(1) | |

O(lgn) | |

O(n) | |

O(nlgn) |

Question 11 Explanation:

The time complexity to build a heap of n elements is O(n).

Build-Max-Heap(A)

// Input: A: an (unsorted) array

// Output: A modified to represent a heap.

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.

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

In a heap, every element is __________ of all the elements in the subtree.

maximum | |

minimum | |

sum | |

product | |

None of the above |

Question 12 Explanation:

Heap is complete binary tree. Sometimes we are calling as binary heap that may be either Max heap or Min heap.

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.

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

A priority queue is implemented as a max-heap. Initially, it has ve elements. The level-order traversal of the heap is as follows:
20, 18, 15, 13, 12
Two new elements ‘10’ and ‘17’are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is:

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 13 Explanation:

There are 13 questions to complete.