Doubt:
To order arrays with heapsort, it is customary to simulate trees with up to two children per parent, not more. My question is whether there are studies, implementations, experiments, reports, accessible data that investigate the performance of heapsort in arrays simulating trees with larger numbers of children per parent.
Details:
I've implemented array sorting with heapsort using up to two children per parent. With the notions of code complexity I have, it seemed to me that the number of comparisons of a heapsort interaction (definition of the last element of the current subarray) is, in the worst case, around 2*log2(n) , since there are two comparisons per level depth and the depth is around log2(n) . But what if I "adopted more children"?
Thinking about this, I suppose we can adapt the code to more than two children by adding, for each additional child, a depth-level comparison. It increases the comparisons by depth, but the depth decreases, thus perhaps making fewer comparisons. The formula I found to estimate the comparisons by interaction depending on the% number of children% is F .
If I'm right, mathematically the ideal would be F*logF(n) , but it does not. Increasing from two children to three children would decrease the number of comparisons (% with% as% with%). Increase from two to four children, you would retain (% with% as% with%). Increasing from two to five children or more would increase comparisons (% with% if% with%). Anyway, mathematically it is like this, but how is the performance in practice? Have you tested it yet? Is there known data?