Question

Remarks: In all algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. Do not write a program. Write pseudo codes or explain in words

Question 4: Recall the problem in which you have k sorted array each of size n, which need to make one single sorted array. Find another fast way to unite the arrays that does not use Priority Queue.

Answer 1

1. The process might begin with merging arrays into groups of two. After the first merge, we have k/2 arrays. Again merge arrays in groups, now we have k/4 arrays. This is similar to merge sort. Divide k arrays into two halves containing an equal number of arrays until there are two arrays in a group. This is followed by merging the arrays in a bottom-up manner.

• Algorithm:
  1. Create a recursive function which takes k arrays and returns the output array.
  2. In the recursive function, if the value of k is 1 then return the array else if the value of k is 2 then merge the two arrays in linear time and return the array.
  3. If the value of k is greater than 2 then divide the group of k elements into two equal halves and recursively call the function, i.e 0 to k/2 array in one recursive function and k/2 to k array in another recursive function.
  4. Print the output array.

2. Using Min Heap : This MinHeap based solution has the same time complexity which is O(NK log K). But for a different and particular sized array, this solution works much better. The process must start with creating a MinHeap and inserting the first element of all the k arrays. Remove the root element of Minheap and put it in the output array and insert the next element from the array of removed element. To get the result the step must continue until there is no element in the MinHeap left.
MinHeap: A Min-Heap is a complete binary tree in which the value in each internal node is smaller than or equal to the values in the children of that node. Mapping the elements of a heap into an array is trivial: if a node is stored at index k, then its left child is stored at index 2k + 1 and its right child at index 2k + 2.

• Algorithm:
  1. Create a min Heap and insert the first element of all k arrays.
  2. Run a loop until the size of MinHeap is greater than zero.
  3. Remove the top element of the MinHeap and print the element.
  4. Now insert the next element from the same array in which the removed element belonged.
  5. If the array doesn’t have any more elements, then replace root with infinite.After replacing the root, heapify the tree.