Purchase Solution

Merging Sorted Lists Using Heaps

Not what you're looking for?

Ask Custom Question

I need help figuring out an algorithm that will merge k sorted lists into one sorted lists in O(n lg k) time where n is the number of elements in ALL the input lists.

I believe we are supposed to use a Heap for k-way merging.

Purchase this Solution
Solution Summary

This solution assists in merging sorted lists using heaps.

Solution Preview

Yes, you can do it with (binary) heaping in O(n log k) time

I assume that you have some familiarity with heaps and/or access to appropriate books or notes.

For definiteness, let us use a Min-Heap.

We need here to recall only the following 3 properties of heaps:

- A Heap is a nearly complete binary tree and, given k items, they can be arranged into a Heap in a O(k log k ) time.

- If the root of a Heap is replaced by a new item, the whole structure can be "heapified", that is the new item can trickle down to such a node as to make the tree a heap again, in O(log k) time.

- The root of a Min-Heap is the minimum of all its elements

Now let ...

Purchase this Solution
Free BrainMass Quizzes
Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

Basic Networking Questions

This quiz consists of some basic networking questions.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

View More Free Quizzes
Related BrainMass Solutions

  • Java data structures and alg.

    The lists must be randomly generated. For each of these list lengths, run the program written for question 1 five times using a different random number seed each time. Average the results.

  • Merging Arrays in VB.NET

    127850 Merging Arrays (Must be in vb.NET) Merging is the process of combining two sorted lists into a single sorted list. In some cases, one list can be appended to the other, and the new list then can be sorted.

  • Sorting Algorithms Comparison

    This is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists Merge O(n log n) O(n log n) O(n log n) O(n) auxiliary space Yes Merging Takes advantage of the ease of merging already sorted lists into a new sorted

  • Merge Sort : splitting and merging trees

    108929 Merge Sort : splitting and merging trees Sort the given sequence of numbers using merge sort. Draw the splitting and merging trees for each application of the procedure.

  • A client function that merges two instances of the Sorted List ADT

    576360 Merged Lists Write a client function that merges two instances of the Sorted List ADT using the following specification.

  • Sorting in Java

    • The rest resulting arrays would be: 80 60 35 25 15 30 80 60 35 30 15 25 80 60 35 30 25 15 - the final sorted array. b) the buble sort.

  • Design and Analysis of Algorithms

    b) Design an algorithm that solves the above problem using a mandatory heap and has time complexity O(m + k*lg(m)) and space complexity O(m).

  • Search using a divide-and-conquer algorithm

    140659 Search using a divide-and-conquer algorithm Design and analyze a divide-and-conquer algorithm for finding the maximum element in a list L[0:n-1]. The assumption is that this list isn't sorted.

  • Recursive definition

    25366 Recursive definition We can define sorted lists of integers as follows: Basis - A list consisting of a single integer is sorted.

View More Related Solutions