CODEWITHSUNDEEP

algorithmlistlinked-list

Reputation: 9421

Merge several pre-sorted lists into a joint list in most effective way (and taking top elements of it )

I have such a pre-set:

many pre-sorted ordered lists, e.g., 1000 elements each sorted by a criteria (for instance, "last" based on a time)
need to make a joint list that maintains sort order and also contains 1000 last elements (so can discard elements of original lists that do not fit into top 1000). However, selecting 1000 top can be done separately as well.
merging needs to be as fast, as efficient as possible. Re-sorting full merged list is not an option.

Upvotes: 0

Views: 163

Answers (2)

Andrianekena Moise

Andrianekena Moise

Reputation: 1068

This problem is known as Merge k sorted arrays. In java, it is quit simple to resolve it. Just add elements into a sortedSet(the add to the sorted set is fast). And stop when you reach the 1000 top.

SortedSet<Integer> s = new TreeSet<>();
//s1,s2,s3 are the input lists here
int n = Math.max(Math.max(s2.size(), s1.size()), s3.size());
for (int i = 0; i < n || s.size() <= limit; i++) {
    if (s1.get(i) != null) {
        s.add(s1.get(i));
    }
    if (s2.get(i) != null) {
        s.add(s2.get(i));
    }
    if (s3.get(i) != null) {
        s.add(s3.get(i));
    }
}

Upvotes: 1

DAle

Reputation: 9127

Use any priority queue-based data structure:

priority queue q = empty
for each list add first element to q
create an array next that contains next elements for every list (initially next element is a second element)

while result list is not full
    take top element from the q and add to the result list
    add next element of the corresponding list to the q (if any)
    update next element of the corresponding list

Upvotes: 4

Related Questions