An optimal algorithm for deleting the root of a heap

DOI10.1016/0020-0190(91)90144-7MaRDI QIDQ750135zbMATH OpenOpenAlexFDO

Authors Svante Carlsson

Publication date 1991

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90144-7

zbMATH Keywords

lower boundupper boundpriority queueHeaps

Mathematics Subject Classification ID

Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• A Note on HEAPSORT
• Parallel heap operations on an EREW PRAM
• Pairing heaps, scrambled pairing and square-root trees
• Algorithm Theory - SWAT 2004
• Optimal heapsort algorithm

Cites work

• A variant of heapsort with almost optimal number of comparisons
• Average-case results on heapsort
• Heaps on Heaps

Cited in

(6)

• 3 is more promising algorithmic parameter than 2
• An in-place priority queue with \(O(1)\) time for push and \(\lg n + O(1)\) comparisons for pop
• An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons
• Best case lower bounds for heapsort
• Optimizing binary heaps
• Revisiting priority queues for image analysis

Describes a project that uses

Uses Software

• heapsort

This page was built for publication: An optimal algorithm for deleting the root of a heap

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