Question

1. Describe the most time-efficient way to implement the operations listed below. Assume no duplicate values and that you can implement the operation as a member function of the class – with access to the underlying data structure. Then, give the tightest possible upper bound for the worst case running time for each operation in terms of N.

Merging two binary min-heaps (both implemented using an array) each containing N elements into a single binary min heap. Explanation:

Answer 1

ANSWER:--

GIVEN THAT:--

Algorithm:

1.) Take and auxillary array of size temp[2N].

2.) Copy elements of first binary heap into temp array from 0 to N-1 then copy elemenst of second binary heap into temp array from N to 2N-1.

3.) Now this temp array should also follow the heap property. So we will build a min-heap of all merged elements together.

----------------------------------------------------------------

Time Complexity:

Copying elements of binary min-heaps into temp array will take time = O(N + N) = O(N)

According to properties of heap data structures building a min or max heap it's worst case time complexity is O(N).

In this way, time complexity to merge two binary min-heaps will be O(N).