Можно ли скрыть мою очередь приоритетов обратно в 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?

Почему вы сортируете с использованием приоритетной очереди? Почему бы не использовать Collections.sort или .stream().sorted(comparator).toList()?

marstran 18.11.2022 16:02

Вы пытаетесь отсортировать все значения Integer по всем LinkedList?

Savior 18.11.2022 16:07

@ Спаситель, да, я пытаюсь их отсортировать

Droid 18.11.2022 16:09

Здравствуйте, вы передаете массив LinkedList в метод, так что именно вы хотите? Просто чтобы отсортировать все элементы в массиве LinkedList, тогда все, что предложил @marstran, ясно.

Sagar Gangwal 18.11.2022 16:09

Как вы думаете, что p.add(x); делает по отношению к такой сортировке?

Savior 18.11.2022 16:15

@Savior Насколько я понимаю приоритетные очереди, при добавлении x (связанного списка) в очередь с помощью p.add(x) он будет отсортирован уже с момента его априорной очереди. Правильно ли я понимаю?

Droid 18.11.2022 16:16

@marstran Мне нужно, чтобы время работы было как можно меньше, поэтому я использовал очередь с приоритетом. Мне нужно, чтобы время выполнения было O (N logk), где N — сумма длин списка, а k = lists.length.

Droid 18.11.2022 16:18

@Droid Но очередь с приоритетом, скорее всего, будет медленнее, чем обычная сортировка списка...

marstran 18.11.2022 16:20

@marstran не время выполнения collections.sort O (nlogn)?

Droid 18.11.2022 16:21

Да, но в этом и сложность Collections.sort. Чего большой O не распознает, так это того, что вам нужно дважды перебрать все элементы, чтобы конвертировать туда и обратно из LinkedList. Так что это накладные расходы, которых вы не получите с Collections.sort.

marstran 18.11.2022 16:26

Вы изменили свой комментарий, пока я писал свой предыдущий комментарий. Выполнение priorityQueue.add(x) для каждого элемента также является O(nlogn), так как add является O(log n)

marstran 18.11.2022 16:27

@marstran Можете ли вы сказать о сложности Collections.sort, когда вы не знаете реализацию списка? Разве поиск LinkedList не медленный, например. ArrayList .get - это O (1), но LinkedList - это O (N), поэтому переход на новый тип данных может улучшить код?

matt 18.11.2022 16:32

Разве ваша приоритетная очередь не должна быть просто PriorityQueue<Integer>, разве это не то, где вы хотите отсортировать Integers

matt 18.11.2022 16:36

@matt Я пытался сделать PriorityQueue<Integer>, но потом не смог выполнить метод add()

Droid 18.11.2022 16:39

@matt, извини, только что увидел твой ответ

Droid 18.11.2022 16:39

@matt Я неявно имел в виду Collections.sort со связанным списком. Должен был указать.

marstran 18.11.2022 16:49

@marstran Я проверяю, Collections.sort просто делегирует List.sort, который для LinkedList использует реализацию по умолчанию. Реализация по умолчанию создает Object[] и затем использует Arrays.sort. Таким образом, ArrayList, LinkedList будет иметь такое же поведение.

matt 19.11.2022 14:31
Документирование API с помощью Swagger на Springboot
Документирование API с помощью Swagger на Springboot
В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .
Как включить TLS в gRPC-клиенте и сервере : 2
Как включить TLS в gRPC-клиенте и сервере : 2
Здравствуйте! 🙏🏻 Надеюсь, у вас все хорошо и добро пожаловать в мой блог.
Сортировка hashmap по значениям
Сортировка hashmap по значениям
На Leetcode я решал задачу с хэшмапой и подумал, что мне нужно отсортировать хэшмапу по значениям.
Принципы SOLID - лучшие практики
Принципы SOLID - лучшие практики
SOLID - это аббревиатура, обозначающая пять ключевых принципов проектирования: принцип единой ответственности, принцип "открыто-закрыто", принцип...
gRPC на Android с использованием TLS
gRPC на Android с использованием TLS
gRPC - это относительно новая концепция взаимодействия между клиентом и сервером, но не более.
0
17
57
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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]

Спасибо за ваш ответ. Если возможно, не могли бы вы также показать, как это можно сделать с помощью очереди с приоритетом, так как я просто хочу знать, какой метод. Например, что я должен редактировать в своем коде?

Droid 18.11.2022 16:38
Ответ принят как подходящий

Я думаю, вы должны изменить несколько вещей, если я понимаю проблему. Сначала сделайте PriorityQueue набором целых чисел, а не списком.

PriorityQueue<Integer> p = new PriorityQueue<>();

Второй в вашем цикле.

p.addAll(x);

Тогда ваша ошибочная строка должна быть правильной

Другие вопросы по теме