Объединить несколько предварительно отсортированных списков в объединенный список наиболее эффективным способом (и взять его верхние элементы)

Question

У меня есть такой предварительный набор:

• много предварительно отсортированных упорядоченных списков, например, 1000 элементов, каждый из которых отсортирован по критериям (например, «последний» по времени)
• необходимо создать объединенный список, который поддерживает порядок сортировки, а также содержит 1000 последних элементов (поэтому можно отбрасывать элементы исходных списков, которые не вписываются в топ 1000).Тем не менее, выбор 1000 top также может быть сделан отдельно.
• объединение должно быть максимально быстрым и эффективным.Пересортировка полного объединенного списка не возможна.

Answer 1

Эта проблема известна как объединение отсортированных массивов.В Java это довольно просто решить.Просто добавьте элементы в sortedSet (добавление в отсортированный набор происходит быстро).И остановитесь, когда достигнете вершины 1000.

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));
    }
}

Answer 2

Использовать любую очередь приоритетов структура данных на основе:

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