Weak-heap sort |
| |
Authors: | Ronald D Dutton |
| |
Institution: | (1) Dept. of Computer Science, University of Central Florida, 32816 Orlando, FL, USA |
| |
Abstract: | A data structure called aweak-heap is defined by relaxing the requirements for a heap. The structure can be implemented on a 1-dimensional array with one extra bit per data item and can be initialized withn items using exactlyn–1 data element compares. Theoretical analysis and empirical results indicate that it is a competitive structure for sorting. The worst case number of data element comparisons is strictly less than (n–1) logn+0.086013n and the expected number is conjectured to be approximately (n–0.5)logn–0.413n. |
| |
Keywords: | E 1 F2 2 |
本文献已被 SpringerLink 等数据库收录! |
|