文章基本信息

标题：On the performance of WEAK-HEAPSORT
本地全文：下载
作者：Stefan Edelkamp, Ingo Wegener
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：heapsort, priority queues, Sorting algorithms