On Sorting, Heaps, and Minimum Spanning Trees
Author
Abstract
Let A be a set of size m. Obtaining the first k ≤ m elements of A in ascending order can be
done in optimal O(m + k log k) time. We present Incremental Quicksort (IQS), an algorithm
(online on k) which incrementally gives the next smallest element of the set, so that the first
k elements are obtained in optimal expected time for any k. Based on IQS, we present the
Quickheap (QH), a simple and efficient priority queue for main and secondary memory. Quickheaps
are comparable with classical binary heaps in simplicity, yet are more cache-friendly. This
makes them an excellent alternative for a secondary memory implementation. We show that
the expected amortized CPU cost per operation over a Quickheap of m elements is O(logm),
and this translates into O((1/B) log(m/M)) I/O cost with main memory size M and block size
B, in a cache-oblivious fashion. As a direct application, we use our techniques to implement
classical Minimum Spanning Tree (MST) algorithms. We use IQS to implement Kruskal’s MST
algorithm and QHs to implement Prim’s. Experimental results show that IQS, QHs, external
QHs, and our Kruskal’s and Prim’s MST variants are competitive, and in many cases better
in practice than current state-of-the-art alternative (and much more sophisticated) implemen-
tations.
Patrocinador
Supported in part by the Millennium Nucleus Center for Web Research, Grant P04-067-F, Mideplan, Chile;
Yahoo! Research grant “Compact Data Structures”; and Fondecyt grant 1-080019, Chile.
Identifier
URI: https://repositorio.uchile.cl/handle/2250/125373
Collections