DAY-4 DSA BOOTCAMP HEAP

Given two max heaps of size n each, what is the minimum possible time complexity to make a one max-heap of size from elements of two max heaps?

• O(n^2)

• O(nLogLogn)

• O(n)

• O(nLogn)

Answer explanation

We can build a heap of 2n elements in O(n) time. Following are the steps. Create an array of size 2n and copy elements of both heaps to this array. Call build heap for the array of size 2n. Build heap operation takes O(n) time.

Which of the following Binary Min Heap operation has the highest time complexity?

• Inserting an item under the assumption that the heap has capacity to accommodate one more item

• Merging with another heap under the assumption that the heap has capacity to accommodate items of other heap

• Deleting an item from heap

• Decreasing value of a key

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

• 40, 30, 20, 10, 15, 16, 17, 8, 4, 35

• 40, 35, 20, 10, 30, 16, 17, 8, 4, 15

• 40, 30, 20, 10, 35, 16, 17, 8, 4, 15

• 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

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

• 3

• 5

• 2

What is the time complexity of Build Heap operation? 
(Build Heap is used to build a max(or min) binary heap from a given array. Build Heap is used in Heap Sort as a first step for sorting.)

• O(nLogn)

• O(n^2)

• O(n)

• O(logn)

Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16 14 15 10 12 27 28 How many heapify operations have been performed on root of heap?

• 1

• 2

• 3 or 4

• 5 or 6

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

A min- Heap is a complete binary tree.

• True

• False

• Depends on number of nodes

• None of the above

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) theta(logn) (B) theta(n) (C) theta(nlogn) (D) theta(n^2)

• A

• B

• C

• D

What are the necessary condition for a Tree to be a heap?

• The tree must be complete.

• Every Root value is greater or smaller than the children's value.

• Both A and B

• None of the above