An optimal algorithm for deleting the root of a heap

DOI10.1016/0020-0190(91)90144-7zbMath0713.68018OpenAlexW2075430515MaRDI QIDQ750135

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

upper boundlower boundpriority queueHeaps

Mathematics Subject Classification ID

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

Related Items (6)

An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons ⋮ An In-Place Priority Queue with O(1) Time for Push and $$\lg n + O(1)$$ lg n + O ( 1 ) Comparisons for Pop ⋮ 3 is more promising algorithmic parameter than 2 ⋮ Optimizing binary heaps ⋮ Revisiting priority queues for image analysis ⋮ Best case lower bounds for heapsort

Uses Software

• heapsort

Cites Work

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

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