Алгоритм переподготовки. Почему heapsort является алгоритмом сортировки?

15

Я не могу понять, почему heapsort считается алгоритмом сортировки по месту .

Я имею в виду дополнительную структуру данных, заполненную элементами сортируемого массива, например кучей, которая используется для извлечения минимального значения и процесса сортировки.

Так может быть, я неправильно понимаю определение здесь?

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

Так почему это считается на месте?

user10326
источник

Ответы:

12

Я имею в виду дополнительную структуру данных, заполненную элементами сортируемого массива, например кучей, которая используется для извлечения минимального значения и процесса сортировки.

Нет. Массив преобразуется для соответствия ограничению кучи без использования более чем O (1) дополнительной памяти. (На самом деле все, что вам нужно, это дополнительная память, достаточная для хранения одного элемента массива, для целей подкачки, плюс логическое значение или два и переменная цикла или два).

Хорошо, с технической точки зрения может случиться так, что heapsort обычно объясняется как использование отдельной кучи, но это вполне возможно реализовать на месте.

Питер Тейлор
источник
3
Единственное место, где я ожидал бы увидеть «heapsort» с отдельной кучей (в коде), находится на функциональном языке, таком как Haskell, по той же причине, по которой обычный функциональный «Quicksort» тоже не на месте - функциональные программисты любят их списки много, и сортировка на месте является состоящей из состояния - это изменяет состояние массива / что бы ни содержало данные. Страшные кавычки, потому что я на самом деле не согласен с тем, что быстрая сортировка неуместна вообще является быстрой сортировкой или что неуместный heapsort - это вообще heapsort - по крайней мере, без четкого указания, что это не место.
Steve314
1
@ Steve314, я думаю, что я видел некоторый учебный материал, который говорит что-то вроде «поместите его в кучу, а затем вытяните элементы по одному и поместите их в массив». Но только что проверив CLR, я могу сообщить, что они показывают версию на месте.
Питер Тейлор
2
@PeterTaylor: Да, в книге, которую я рецензировал (Skiena), была представлена ​​сортировка путем построения дополнительной кучи.
user10326
4

Возможно, вам не хватает фундаментального понимания того, что массив можно использовать для указания макета дерева.

Предположим, у вас есть двоичное дерево, а внутренний узел находится по индексу i массива. Тогда индекс массива родителя и потомков этого узла можно найти:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

Видеть:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Поскольку куча может храниться и организовываться целиком в массиве, тогда heapsort может работать на месте, перемещая элементы внутри входного массива. Действительно, куча создается и управляется с использованием исходного входного массива.

stackoverflowuser2010
источник
Я знаю об этом. Проблемы, похоже, заключаются в том, что в книге, которую я читаю, была представлена ​​сортировка с использованием отдельной кучи. Я не понимал и не думал, что эта презентация должна была облегчить понимание алгоритма (возможно? Не уверен, почему это было представлен так)
user10326
Я настоятельно рекомендую вам приобрести книгу Cormen et al. "Введение в алгоритмы". Он четко отвечает на все вопросы, связанные с алгоритмом. Если вы серьезно относитесь к карьере ученого-программиста или программиста, то вам нужна эта книга.
stackoverflowuser2010
1

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

Однако, это не так. Вы можете построить кучу на том же массиве, который хотите отсортировать, и после этого вы применяете алгоритм heapsort, чтобы он сортировался на месте.

Даниэль Скокко
источник
По сути, существует алгоритм «heapify», который используется для переупорядочения данных в массиве, чтобы он соответствовал правилам кучи во IIRC O (n) времени. См. Псевдокод на сайте programmers.stackexchange.com/questions/116904/… . После этого, в основном, это вопрос повторных извлечений корня кучи и отслеживания того, какая часть массива все еще является «кучей» и сколько отсортировано в конечном результате.
Steve314
0

В компьютерной науке алгоритм на месте (или на латыни in situ) - это алгоритм, который преобразует входные данные, используя структуру данных с небольшим постоянным объемом дополнительного пространства для хранения. Входные данные обычно перезаписываются выходными данными при выполнении алгоритма. Алгоритм, который не на месте, иногда называют не на месте или не на месте.

Википедия - алгоритм на месте

Рейн Хенрикс
источник
Так почему же тогда mergesort считается алгоритмом не на месте?
user10326
3
Это не полезный ответ. Это не имеет никакого отношения к heapsort и не отвечает на вопрос.
stackoverflowuser2010
Конечно, это как-то связано с heapsort. Heapsort - это алгоритм сортировки на месте, как должно быть ясно из определения. Фактически, это было связано со страницей heapsort.
Рейн Хенрикс
0

Он считается на месте, потому что его требования к пространству незначительны (постоянны или вообще отсутствуют, если вы используете побитовые операции для обмена элементами). Например, MergeSort не существует, поскольку входной набор не изменяется на каждой итерации примера поиска.

Лучший способ проиллюстрировать различия между алгоритмами на месте и алгоритмами на месте - это, вероятно, взглянуть на следующий код обращения к строкам C / C ++, который делает это на месте (из K & R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

Если бы вы, например, читали входную строку с конца и помещали символы в другой буфер, это был бы алгоритм обращения строки не к месту.

rdasxy
источник
1
Mergesort чертовски раздражает - легко ошибочно убедить себя, что у вас есть стратегия на месте. Обычно это работает только для небольших массивов. Тем не менее, я думаю , что я скачал бумагу раз , когда кто - то сделало разработает вариант на месте алгоритма слияния-сортировке. Я посмотрю, смогу ли я найти это снова.
Steve314