Можно ли скрыть мою очередь приоритетов обратно в LinkedList<Integer>?
Мне даны k номера LinkedList<Integer>, и я пытаюсь поместить их в PriorityQueue p, чтобы отсортировать.
Однако у меня возникли проблемы с попыткой преобразовать его обратно в LinkedList<Integer> из приоритетной очереди, которую я объявил.
Вот мой код:
//Code by Dave S.
public class MultiMergeWay {
public static LinkedList<Integer> mergeAll(LinkedList<Integer>[] lists){
PriorityQueue<LinkedList<Integer>> p = new PriorityQueue<>();
for(LinkedList<Integer> x : lists){
p.add(x);
}
LinkedList<Integer> array_list = new LinkedList<Integer>(p); //
return array_list;
}
}
Если вы еще этого не видели, мой код даже не скомпилируется из-за ошибки в строке, отмеченной //.
Может ли кто-нибудь объяснить, как я могу изменить свою приоритетную очередь обратно на LinkedList?
Вы пытаетесь отсортировать все значения Integer по всем LinkedList?
@ Спаситель, да, я пытаюсь их отсортировать
Здравствуйте, вы передаете массив LinkedList в метод, так что именно вы хотите? Просто чтобы отсортировать все элементы в массиве LinkedList, тогда все, что предложил @marstran, ясно.
Как вы думаете, что p.add(x); делает по отношению к такой сортировке?
@Savior Насколько я понимаю приоритетные очереди, при добавлении x (связанного списка) в очередь с помощью p.add(x) он будет отсортирован уже с момента его априорной очереди. Правильно ли я понимаю?
@marstran Мне нужно, чтобы время работы было как можно меньше, поэтому я использовал очередь с приоритетом. Мне нужно, чтобы время выполнения было O (N logk), где N — сумма длин списка, а k = lists.length.
@Droid Но очередь с приоритетом, скорее всего, будет медленнее, чем обычная сортировка списка...
@marstran не время выполнения collections.sort O (nlogn)?
Да, но в этом и сложность Collections.sort. Чего большой O не распознает, так это того, что вам нужно дважды перебрать все элементы, чтобы конвертировать туда и обратно из LinkedList. Так что это накладные расходы, которых вы не получите с Collections.sort.
Вы изменили свой комментарий, пока я писал свой предыдущий комментарий. Выполнение priorityQueue.add(x) для каждого элемента также является O(nlogn), так как add является O(log n)
@marstran Можете ли вы сказать о сложности Collections.sort, когда вы не знаете реализацию списка? Разве поиск LinkedList не медленный, например. ArrayList .get - это O (1), но LinkedList - это O (N), поэтому переход на новый тип данных может улучшить код?
Разве ваша приоритетная очередь не должна быть просто PriorityQueue<Integer>, разве это не то, где вы хотите отсортировать Integers
@matt Я пытался сделать PriorityQueue<Integer>, но потом не смог выполнить метод add()
@matt, извини, только что увидел твой ответ
@matt Я неявно имел в виду Collections.sort со связанным списком. Должен был указать.
@marstran Я проверяю, Collections.sort просто делегирует List.sort, который для LinkedList использует реализацию по умолчанию. Реализация по умолчанию создает Object[] и затем использует Arrays.sort. Таким образом, ArrayList, LinkedList будет иметь такое же поведение.
Ответы 2
Попробуйте ответить ниже. Для сортировки LinkedList вам не нужно использовать PriorityQueue. Это просто возможно с помощью метода sorted() потокового API, который может вам помочь.
Поскольку вы используете Array of LinkedList , потоковый API Java 8 предоставляет flatMap сопоставитель функций, который будет сглаживать несколько списков, а затем просто применять сортировку.
Это поможет вам.
public class MultiMergeWay {
public static void main(String[] args) {
LinkedList<Integer> array_list = new LinkedList<>(Arrays.asList(new Integer[]{100, 500, 80}));
LinkedList<Integer> array_list1 = new LinkedList<>(Arrays.asList(new Integer[]{200, 600, 90}));
LinkedList<Integer> array_list2 = new LinkedList<>(Arrays.asList(new Integer[]{1200, 700, 80}));
mergeAll(new LinkedList[]{array_list, array_list1, array_list2});
}
public static LinkedList<Integer> mergeAll(LinkedList<Integer>[] array) {
System.out.println("Before ==>" + array[0] + " " + array[1] + "" + array[2]);
var result = Stream.of(array).flatMap(Collection::stream).sorted().collect(Collectors.toList());
System.out.println("After ==>" + result);
return new LinkedList<>(result);
}
}
Вывод
До ==>[100, 500, 80] [200, 600, 90][1200, 700, 80]
После ==> [80, 80, 90, 100, 200, 500, 600, 700, 1200]
Спасибо за ваш ответ. Если возможно, не могли бы вы также показать, как это можно сделать с помощью очереди с приоритетом, так как я просто хочу знать, какой метод. Например, что я должен редактировать в своем коде?
Я думаю, вы должны изменить несколько вещей, если я понимаю проблему. Сначала сделайте PriorityQueue набором целых чисел, а не списком.
PriorityQueue<Integer> p = new PriorityQueue<>();
Второй в вашем цикле.
p.addAll(x);
Тогда ваша ошибочная строка должна быть правильной
Почему вы сортируете с использованием приоритетной очереди? Почему бы не использовать
Collections.sortили.stream().sorted(comparator).toList()?