On sorting, heaps, and minimum spanning trees

DOI10.1007/s00453-010-9400-6zbMath1209.68177OpenAlexW2094173296MaRDI QIDQ973020

Rodrigo Paredes, Gonzalo Navarro

Publication date: 28 May 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/141836

zbMATH Keywords

priority queuesexternal priority queuesincremental sortingKruskal's MST algorithmPrim's MST algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items (3)

STRONGER QUICKHEAPS ⋮ Cascade heap: towards time-optimal extractions ⋮ Cascade heap: towards time-optimal extractions

Uses Software

• R
• STXXL
• Find
• heapsort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• BOTTOM-UP-HEAPSORT, and new variant of HEAPSORT beating, on an average, QUICKSORT (if \(n\) is not very small)
• The pairing heap: A new form of self-adjusting heap
• Time bounds for selection
• Heaps and heapsort on secondary storage
• Organization and maintenance of large ordered indexes
• Cache-Oblivious Algorithms
• Faster algorithms for the shortest path problem
• On the limits of cache-obliviousness
• Amortized Computational Complexity
• Finding Minimum Spanning Trees
• Design and implementation of an efficient priority queue
• A data structure for manipulating priority queues
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Self-Adjusting Heaps
• A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
• The birth of the giant component
• Fast priority queues for cached memory
• An experimental study of priority queues in external memory
• Algorithms - ESA 2003

This page was built for publication: On sorting, heaps, and minimum spanning trees