Вопрос по алгоритму сортировки кучи

Question

Я рассматриваю алгоритм Heap Sort . Мне интересно, почему это реализовано в бинарном дереве? Может ли оно использовать другое дерево? Например, дерево с тремя дочерними узлами? Или четыре? С большим количеством дочерних элементов, хотя требуется немного больше сравнения для операции удаления. высота дерева может быть уменьшена намного больше . Я считаю, что затраты времени должны упасть значительно по сравнению с реализацией двоичного дерева.

Answer 1

Википедия также показывает разницу в стоимости - она ​​составляет всего 12%. Высота дерева должна уменьшаться с коэффициентом log (3) / log (2) ~ = 1,5

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

Answer 2

Согласно Википедии, троичный порт быстрее, но сложнее в реализации.