On Sorting, Heaps, and Minimum Spanning Trees
Gonzalo Navarro and Rodrigo Paredes
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(log m), 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 case better in practice than current state-of-the-art alternative
(and much more sophisticated) implementations.