Name
Abstract | ||
|---|---|---|
A new algorithm for rearranging a heap is presented and analysed in the average case. The average case upper bound for deleting the maximum element of a random heap is improved, and is shown to be less than [logn]+0.299+M(n) comparisons, *) whereM(n) is between 0 and 1. It is also shown that a heap can be constructed using 1.650n+O(logn) comparisons with this algorithm, the best result for any algorithm which does not use any extra space. The expected time to sortn elements is argued to be less thann logn+0.670n+O(logn), while simulation result points at an average case ofn log n+0.4n which will make it the fastest in-place sorting algorithm. The same technique is used to show that the average number of comparisons when deleting the maximum element of a heap using Williams' algorithm for rearrangement is 2([logn]−1.299+L(n)) whereL(n) also is between 0 and 1, and the average cost for Floyd-Williams Heapsort is at least 2nlogn−3.27n, counting only comparisons. An analysis of the number of interchanges when deleting the maximum element of a random heap, which is the same for both algorithms, is also presented. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1007/BF01937350 | BIT |
Keywords | Field | DocType |
average-case analysis,heaps,heapsort.,average-case result,sorting,priority queues,upper bound,sorting algorithm,priority queue | Discrete mathematics,Binary logarithm,Combinatorics,Upper and lower bounds,Heapsort,Queue,Heap (data structure),Average cost,Sorting algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 1 | 0006-3835 |
Citations | PageRank | References |
27 | 2.92 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Svante Carlsson | 1 | 764 | 90.17 |