Heaps on Heaps

DOI10.1137/0215068zbMath0619.68042OpenAlexW1995675812MaRDI QIDQ3756520

J. Ian Munro, Gaston H. Gonnet

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215068

zbMATH Keywords

lower boundscomplexity of comparison based problemspriority queue operations on a heap

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05)

Related Items (22)

An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons ⋮ Merging heaps in parallel ⋮ An In-Place Priority Queue with O(1) Time for Push and $$\lg n + O(1)$$ lg n + O ( 1 ) Comparisons for Pop ⋮ Recurrence relations on heaps ⋮ A note on constructing min-max heaps ⋮ Optimizing binary heaps ⋮ A characterization of heaps and its applications ⋮ Two-tier relaxed heaps ⋮ Heaps with bits ⋮ QuickHeapsort: modifications and improved analysis ⋮ Best case lower bounds for heapsort ⋮ Sorting using heap structure ⋮ Two skew-binary numeral systems and one application ⋮ Parallel heap: an optimal parallel priority queue ⋮ An efficient data structure for branch-and-bound algorithm ⋮ Unnamed Item ⋮ A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort ⋮ QuickXsort: a fast sorting scheme in theory and practice ⋮ An optimal algorithm for deleting the root of a heap ⋮ Building heaps in parallel ⋮ A Survey on Priority Queues ⋮ On constant factors in comparison-based geometric algorithms and data structures

This page was built for publication: Heaps on Heaps