Внедрение heapsort без использования отдельной структуры данных кучи

Question

Я хочу реализовать heapsort без использования структуры данных кучи. Точнее, я хочу, чтобы все изменения выполнялись в исходном массиве. Я попытался реализовать его, но я застрял, потому что он превращается в другой алгоритм, например, сортировку выбора или сортировку пузырьков. Итак, какой тип будет называться хапсортом при условии, что мы не будем использовать структуру данных кучи?

Answer 1

Увлекательная вещь о куче заключается в том, что ее можно реализовать просто как расположение элементов в массиве - для элементов не требуется отдельная структура данных с указателями. Greybeard указывает вам на страницу wikipedia, которая очень хорошо относится к этому, но вкратце идея состоит в том, чтобы построить кучу на месте, заменяя элементы, а затем сортировать, снова путем замены элементов в том же массиве.