Я не уверен, что вы подразумеваете под 1 кучей. Используя стандартную терминологию, 1-куча будет кучей с одним дочерним элементом на узел: связанный список. Это не очень хорошо работает.
3-куча - это просто d -ary куча , где d = 3. Вы говорите, что сортировка кучи использует 2 кучи. Это не всегда так. Многие люди реализуют сортировку кучи с 2 кучами, часто потому, что они не знают, что могут использовать 3 кучи. К сожалению, 3-куча может быть более эффективной во многих случаях. У меня и многих других есть реализованная сортировка кучи с 3 кучами.
Если под "кучей n-1" вы подразумеваете кучу с n-1 дочерними элементами корня, это не будет очень эффективным. С n-1 дочерними элементами корня, когда вы удаляете наименьший элемент, вы должны искать всех n-1 дочерних элементов, чтобы найти новый корень. Вы также можете просто многократно искать линейный список для следующего по величине элемента. Сортировка кучи "n-1" будет иметь ту же производительность, что и сортировка выбора.
Сбалансированное бинарное дерево поиска будет работать лучше, чем несбалансированное, но построить дерево дорого. Красота сортировки кучи в том, что вы можете построить кучу в O (n), на месте. Построение BST - это O (n log n). Хотя удаление наименьшего узла является операцией O (log n) для обоих, производительность в реальном мире благоприятствует куче.
При этом любая структура данных, которая может служить приоритетной очередью, может использоваться в сортировке на основе pq. Двоичная куча (в общем случае d -ary куча) обычно используется, потому что она проста в реализации и очень эффективна. Однако, в зависимости от вашего приложения, что-то вроде сопряженная куча может потенциально превзойти двоичную кучу.