Author | dc.contributor.author | Navarro, Gonzalo | |
Author | dc.contributor.author | Paredes, Rodrigo | es_CL |
Admission date | dc.date.accessioned | 2010-06-23T20:34:14Z | |
Available date | dc.date.available | 2010-06-23T20:34:14Z | |
Publication date | dc.date.issued | 2006 | |
Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/125373 | |
Abstract | dc.description.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. | en_US |
Patrocinador | dc.description.sponsorship | 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. | en_US |
Lenguage | dc.language.iso | en | en_US |
Keywords | dc.subject | Kruskal’s MST algorithm | en_US |
Título | dc.title | On Sorting, Heaps, and Minimum Spanning Trees | en_US |
Document type | dc.type | Artículo de revista | |