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+ klog 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 Krusk
%0 Journal Article
%1 5013309720100801
%A Navarro, Gonzalo
%A Paredes, Rodrigo
%D 2010
%J Algorithmica
%K 2010 kde seminar sortingalgorithm
%N 4
%P 585 - 620
%T On Sorting, Heaps, and Minimum Spanning Trees.
%U http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=50133097&site=ehost-live
%V 57
%X 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+ klog 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 Krusk
@article{5013309720100801,
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+ klog 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 Krusk},
added-at = {2010-06-08T16:09:37.000+0200},
author = {Navarro, Gonzalo and Paredes, Rodrigo},
biburl = {https://www.bibsonomy.org/bibtex/2519ccd1bc2ef51231ff7a9bd0fed6802/kw},
interhash = {863d72d3fb0ef66447aaa917a7caacdb},
intrahash = {519ccd1bc2ef51231ff7a9bd0fed6802},
issn = {01784617},
journal = {Algorithmica},
keywords = {2010 kde seminar sortingalgorithm},
number = 4,
pages = {585 - 620},
timestamp = {2010-06-08T16:09:59.000+0200},
title = {On Sorting, Heaps, and Minimum Spanning Trees.},
url = {http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=50133097&site=ehost-live},
volume = 57,
year = 2010
}