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