Сортировка одной кучи?

Некоторое время назад нам было поручено написать программу на языке переменного тока, которая сортирует массив из n чисел, используя d-арную максимальную кучу (кучу, в которой каждый узел имеет до d дочерних узлов). Программа должна была попросить пользователя ввести значение d, значение от 2 до размера массива. Когда я проверял свою программу, я случайно ввел 1 в качестве значения d, и каким-то образом алгоритму удалось правильно отсортировать массив, используя 1-арную кучу, хотя это заняло намного больше времени, чем обычные значения d.

Как такое возможно? Одномерная куча - это даже не куча, это просто список, у каждого узла есть только один дочерний элемент. Может ли кто-нибудь объяснить, как может происходить такая сортировка?

6
задан j0k 6 March 2013 в 16:53
поделиться