I am reviewing the Heap Sort Algorithm. I am wondering why it is implemented in binary tree? Could it use other tree? Such as a three-child-node tree? Or four? With more child count, though a little more comparison is needed for deletion operation. the height of the tree can be reduced much more. I believe the time cost should drop significantly compared to the binary tree implementation.
+1
A:
According to Wikipedia, a ternary heapsort is faster, but more complicated to implement.
SLaks
2010-10-10 13:10:25
+1
A:
Wikipedia also shows a cost difference - it's only 12%. Tree height should decresae by factor of log(3)/log(2) ~= 1.5
You get that for the price of overly complicated code and risk of having more bugs. Usually when heapsort performance is not satysfying you look for another algorithm. That can give you much more performance gain.
rawicki
2010-10-10 14:33:48