Куча сортировать связанный список

Question

Я пытаюсь создать функцию сортировки в c ++, которая сортирует связанный объект списка, используя сортировку Heap, но я не знаю, с чего начать.Кто-нибудь может дать мне представление о том, как это сделать?Я даже не уверен, как бы отсортировать связанный список

Answer 1

Heapsort работает путем построения heap из данных. Куча эффективна только тогда, когда у вас есть произвольный доступ к каждому элементу.

Первым шагом будет создание массива указателей на объекты списка, чтобы вы могли выполнить обычную сортировку кучи для массива.

Последним шагом будет преобразование вашего массива указателей обратно в связанный список.

Лучшим методом сортировки для связанного списка является сортировка вставкой - не в последнюю очередь потому, что вы можете выполнить сортировку как часть функции insert() реализации связанного списка.

Answer 2

HeapSort хорош по двум причинам -
1 - это алгоритм на месте.
2 - временная сложность O (nlogn)

O (nlogn) из-за произвольного доступаприрода массива, но если вы используете связанный список, вы не получите преимущества произвольного доступа к массиву.Следовательно, сложность времени станет O (n ^ 2).Это не подходит для сортировки.

Я рекомендую вам использовать алгоритм сортировки слиянием для связанного списка.

Answer 3

Я должен согласиться с ответом Сарнольда. Крайне неэффективно устанавливать кучу списков по ряду причин, но, во-первых, они должны были быть отсортированы при первоначальном размещении. Тем не менее, если бы я собирался попробовать, я бы создал ArrayList<T> links, чтобы загрузить все ссылки в него. Затем вы можете получить это в кучах и отсортировать их. Как только вы закончите, просто перезагрузите свой связанный список, начиная с головы.