ZuoTi.Pro
Question

9. When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can s

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

Answer :

We have two sorted lists of numbers in non-descending order,and we need to merge them into one sorted list.

Firstly we have to construct the min-heap of the k-sublist and each sublist which is a node in the constructed min-heap.
We have several steps to follows:

Step-1. When we compare the two sublists, at the starting we can compare their first elements which is actually their minimum elements.
Step-2. The min-heap formation will cost be O(k) time.
Step-3. After the step 1 & step 2 we can run the minimum algorithm which can be extracted from the minimum element in the root list.
Step-4. Then Update the root list in the heap and after that heapify the min-heap as maintained by the new minimum element in the root list.
Step-5. If any root sub-list becomes empty in the step 4 then we can take any leaf sub-list from the root and heapify it.
Step-6. At every Extraction of the element it can take up to O(log k) time.

Hence, We can say that the extract of n element in the total whose
Running time will be O(n log k + k) which can be equal to the O(n log k+ k) (since k < n).

** Please rate positive if the answer was useful

0 0
Add a comment
Know the answer?
Add Answer to:
9. When we have two sorted lists of numbers in non-descending order, and we need to...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • When we have two sorted lists of numbers in non-descending order, and we need to merge...

    When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can simply compare the first two elements of the lists, extract the smaller one and attach it to the end of the new list, and repeat until one of the two original lists become empty, then we attach the remaining numbers to the end of the new list and it's done. This takes linear time. Now, try to...

  • 1. Design an algorithm to find all the non-common elements in two sorted lists of numbers....

    1. Design an algorithm to find all the non-common elements in two sorted lists of numbers. What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n, ?respectively 2. Estimate how many times faster it will be to find ged(98765, 56789) by Euclid's algorithm compared with the algorithm based on checking consecutive integers from min{m, n} down to gcd(m, n). 3. For each of the following functions, indicate how...

  • Discrete Mathematics Unsorted and Sorted Lists For linear search there was no requirement for the list...

    Discrete Mathematics Unsorted and Sorted Lists For linear search there was no requirement for the list to be organized in any manner. The linear search works for lists that are "unsorted." But what if the values in the list are given in ascending order? This would be a sorted list. With a sorted list, is there a more efficient way to find the target? Unsorted Lists (4 pts) Assume there is a sorting algorithm with order of growth O(n), where...

  • Puodace a char showing the number of moves required to solve the Towers of Hanoi puzle using t 30...

    Puodace a char showing the number of moves required to solve the Towers of Hanoi puzle using t 30. What is an execution frame? What is an activation record? What is contained in it? 31. Write a recursive Java method that computes the factorial of a number 2. Linear search may require up to comparisons while binary search will only require roughly comparisons 33. Sort sorts a list of values by repetitively putting a particular value into its final, sorted,...

  • Optimal Merge Pattern - We saw from MergeSort that merging two sorted files together (one size...

    Optimal Merge Pattern - We saw from MergeSort that merging two sorted files together (one size m and one size n) took O(m+n) time. When merging multiple sorted files together, the merge can be accomplished by repeatedly merging sorted files in pairs. For example X1, X2, X3 are three sorted files of length 30, 20 and 10. There are multiple ways to merge them two-at-a-time (with the appropriate costs): (X1 merge X2) merge X3 X1 merge (X2 merge X3) (X1...

  • C programing Write a program to sort numbers in either descending or ascending order. The program...

    C programing Write a program to sort numbers in either descending or ascending order. The program should ask the user to enter positive integer numbers one at a time(hiting the enter key after each one) The last number entered by the user should be -1, to indicate no further numbers will be entered. Store the numbers in an array, and then ask the user how to sort the numbers (either descending or ascending). Call a function void sortnumbers ( int...

  • problem 2 can use Det-Selection(A, p, q, r) as a sub-routine (i.e, you don't need to...

    problem 2 can use Det-Selection(A, p, q, r) as a sub-routine (i.e, you don't need to write its pseudo-code). To sort an array A, you will then call Det-QuickSort(A, 1, n). You also need to provide the worst case time complexity analysis of your algorithm. 2. (20 points) Given a set of n distinct numbers, we wish to find the k largest in sorted order using a comparison-based algorithm. Give an algorithm that implements each of the following methods, and...

  • 3. (20 pts.) You are given two sorted lists of numbers with size m and n....

    3. (20 pts.) You are given two sorted lists of numbers with size m and n. Give an O(logn+ logm) time algorithm for computing the k-th smallest element in the union of the two lists. 4. (20 pts.) Solve the following recurrence relations and give a bound for each of them. CMPSC 465, Fall 2019, HW 2 (a) T(n) = 117(n/5)+13n!.3 (b) T(n) = 2T (n/4)+nlogn (c) T(n) = 5T (n/3) +log-n (d) T(n) = T(n/2) +1.5" (e) T(n) =...

  • Suppose that we have two unsorted lists of integers A and B. The lists are the...

    Suppose that we have two unsorted lists of integers A and B. The lists are the same size, n. a) Write an algorithm that outputs how many integers occur in both lists. An integer occurs at most once in each given list. For example: if A = [1,2,5,7,13,19] and B = [2,9,13,14,19,22], then we can see that elements {2, 13, 19} occur in both lists, so the output will be 3. b) If the lists were sorted, say how we...

  • (9) Complete the below Java method recursively, which takes in a String and returns if it's...

    (9) Complete the below Java method recursively, which takes in a String and returns if it's a palindrome. Remember a palindrome means a string that is the same reversed, like "deed", "racecar" or "tacocat". The empty string "" is also a palindrome. public boolean isPalindrome (String word) { (8) (a) (8 points) Implement merging two sorted arrays into one sorted ar- ray. These arrays are sorted in descending order. For example, (5, 4, 2). Return an array with all the...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT