NDLI: On Sorting, Heaps, and Minimum Spanning Trees

Content Provider	Springer Nature Link
Author	Navarro, Gonzalo Paredes, Rodrigo
Copyright Year	2010
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 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 cases better in practice than current state-of-the-art alternative (and much more sophisticated) implementations.
Starting Page	585
Ending Page	620
Page Count	36
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	57
Issue Number	4
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2010-03-23
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Kruskal’s MST algorithm Prim’s MST algorithm Incremental sorting Priority queues External priority queues Data Structures, Cryptology and Information Theory Computer Systems Organization and Communication Networks Algorithms Mathematics of Computing Theory of Computation Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Note on the Structure of Kruskal’s Algorithm

RAM-Efficient External Memory Sorting

Faster Swap Edge Computation in Minimum Diameter Spanning Trees

(Incremental) Priority Algorithms

The Stackelberg Minimum Spanning Tree Game

A simpler minimum spanning tree verification algorithm

Optimal parallel verification of minimum spanning trees in logarithmic time

A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest

Near-optimal bounded-degree spanning trees

On Sorting, Heaps, and Minimum Spanning Trees

Similar Documents

Note on the Structure of Kruskal’s Algorithm

RAM-Efficient External Memory Sorting

Faster Swap Edge Computation in Minimum Diameter Spanning Trees

(Incremental) Priority Algorithms

The Stackelberg Minimum Spanning Tree Game

A simpler minimum spanning tree verification algorithm

Optimal parallel verification of minimum spanning trees in logarithmic time

A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest

Near-optimal bounded-degree spanning trees

On Sorting, Heaps, and Minimum Spanning Trees