An optimal algorithm for deleting the root of a heap

DOI10.1016/0020-0190(91)90144-7zbMATH Open0713.68018OpenAlexW2075430515MaRDI QIDQ750135FDOQ750135

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

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

zbMATH Keywords

lower boundupper boundpriority queueHeaps

Mathematics Subject Classification ID

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

Cites Work

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

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

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)