Я не могу понять, почему heapsort считается алгоритмом сортировки по месту .
Я имею в виду дополнительную структуру данных, заполненную элементами сортируемого массива, например кучей, которая используется для извлечения минимального значения и процесса сортировки.
Так может быть, я неправильно понимаю определение здесь?
Но для сортировки вставкой, например, очевидно, что это встроенный алгоритм, т.е. для элементов не требуется дополнительной памяти.
Так почему это считается на месте?
источник
Возможно, вам не хватает фундаментального понимания того, что массив можно использовать для указания макета дерева.
Предположим, у вас есть двоичное дерево, а внутренний узел находится по индексу i массива. Тогда индекс массива родителя и потомков этого узла можно найти:
Видеть:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm
Поскольку куча может храниться и организовываться целиком в массиве, тогда heapsort может работать на месте, перемещая элементы внутри входного массива. Действительно, куча создается и управляется с использованием исходного входного массива.
источник
Если, как вы говорите, для построения кучи действительно нужна дополнительная структура, тогда heapsort действительно НЕ будет алгоритмом сортировки на месте.
Однако, это не так. Вы можете построить кучу на том же массиве, который хотите отсортировать, и после этого вы применяете алгоритм heapsort, чтобы он сортировался на месте.
источник
Википедия - алгоритм на месте
источник
Он считается на месте, потому что его требования к пространству незначительны (постоянны или вообще отсутствуют, если вы используете побитовые операции для обмена элементами). Например, MergeSort не существует, поскольку входной набор не изменяется на каждой итерации примера поиска.
Лучший способ проиллюстрировать различия между алгоритмами на месте и алгоритмами на месте - это, вероятно, взглянуть на следующий код обращения к строкам C / C ++, который делает это на месте (из K & R):
Если бы вы, например, читали входную строку с конца и помещали символы в другой буфер, это был бы алгоритм обращения строки не к месту.
источник