Сортировка кучи, минимальная куча или максимальная?

Question

Для сортировки кучи, если мы хотим отсортировать массив в порядке возрастания, следует ли преобразовывать кучу в максимальную или минимальную кучу?

Answer 1

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

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