Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR99-028 | 30th August 1999 00:00

On the performance of WEAK-HEAPSORT


Authors: Stefan Edelkamp, Ingo Wegener
Publication: 30th August 1999 13:47
Downloads: 1126


Dutton presents a further HEAPSORT variant called
WEAK-HEAPSORT which also contains a new data structure for
priority queues. The sorting algorithm and the underlying
data structure ara analyzed showing that WEAK-HEAPSORT is
the best HEAPSORT variant and that it has a lot of nice
properties. It is shown that the worst case number of
comparisons is smaller than nlog n + 0.1 n and weak heaps
can be generated with n-1 comparisons. A double-ended
priority queue based on weak-heaps can be generated
in 1.5 n -1 comparisons. Moreover, examples for the
worst and the best case of WEAK-HEAPSORT are presented,
the number of Weak-Heaps on {1...n} is determined and
experiments on the average case are reported.

ISSN 1433-8092 | Imprint