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

Question

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

Answer 1

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

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

Answer 2

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