© 1999 by British Computer Society
Near Optimal ß Heap
A1 Department of Computing, Hong Kong Polytechnic University, Kowloon, Hong Kong Email: csrluk@comp.polyu.edu.hk
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.
Received 25 August, 1998. Revised 5 May, 1998.