On sorting, heaps, and minimum spanning trees

DOI10.1007/S00453-010-9400-6zbMATH Open1209.68177OpenAlexW2094173296MaRDI QIDQ973020FDOQ973020

Authors: Gonzalo Navarro, Rodrigo Paredes 

Publication date: 28 May 2010

Published in: Algorithmica (Search for Journal in Brave)

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

Recommendations

• On the heap sort algorithm
• Min-max heaps and generalized priority queues
• On Some Parameters in Heap Ordered Trees
• A note on constructing min-max heaps
• On the ``heap problem
• A Note on HEAPSORT
• On the Best Case of Heapsort
• scientific article; zbMATH DE number 4047086
• An optimal algorithm for selection in a min-heap
• A variant of heapsort with almost optimal number of comparisons

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Pairing heaps, scrambled pairing and square-root trees
• Cascade heap: towards time-optimal extractions
• Cascade heap: towards time-optimal extractions
• Min-max heaps and generalized priority queues
• STRONGER QUICKHEAPS

Uses Software

• R
• STXXL
• Find
• heapsort

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q973020)