1-ка куча? - PullRequest
       36

1-ка куча?

5 голосов
/ 12 декабря 2010

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

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

1 Ответ

7 голосов
/ 12 декабря 2010

1-арная куча по-прежнему является кучей и удовлетворяет всем инвариантам, которые требуются для сортировки кучи:

  • Первый элемент является самым большим элементом.
  • Перколяцияможет переместить верхний элемент вниз в правильное положение.

На практике 1-арная куча - это дерево, в котором у каждого узла есть один дочерний элемент - это также называется односвязным списком.Кроме того, ограничение кучи означает, что дочерний узел меньше, чем родительский узел.Итак, проще говоря, 1-арная куча - это односвязный список, отсортированный в обратном порядке.

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

...