###
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 **QH**s to implement Prim's.
Experimental results show that **IQS**, **QH**s, external **QH**s,
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.