Near Optimal ß Heap

A β heap, after D. B. Johnson, corresponds to an M-ary tree with a branch factor β where every vertex of the tree satisfies the heap property. The β heap was also known as the generalized heap and R-ary heap. In this paper, we prove that the address scheme in previous work is compact and correct. We investigated the global optimal values of β for sift-up, insert, delete-min, make heap and heapsort operations. Although closed form solutions for the global optimal values of β cannot be found, we prove that a (unique) global optimum solution exists for most cases and the equality conditions for optimal values of β are determined. Experiments show that the global optimal value of β for heapsort is approximately 4, which is theoretically a (near) optimal solution for all practical purposes. We show that the β heapsort performance is sensitive to the implementation of heap maintenance and we demonstrate that the speed-up of heap maintenance by microcodes can be achieved using high-level constructs. The speed-up in heapsort between β = 4 and 2 (i.e. binary) is between 10% and 30% where quicksort remains the fastest. If the main concern is the worst-case time complexity and exchange operations are taken into account, a β (= 4) heapsort would be a suitable choice for all practical purposes.