Heaps on Heaps

DOI10.1137/0215068zbMATH Open0619.68042OpenAlexW1995675812MaRDI QIDQ3756520FDOQ3756520

Authors: Gaston H. Gonnet, J. Ian Munro 

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

Recommendations

• scientific article; zbMATH DE number 742986
• Algorithm Theory - SWAT 2004
• Refined complexity analysis for heap operations
• Building heaps fast
• Optimizing binary heaps

zbMATH Keywords

lower boundscomplexity of comparison based problemspriority queue operations on a heap

Mathematics Subject Classification ID

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

Cited In (40)

• Parallel heap: an optimal parallel priority queue
• Title not available (Why is that?)
• Two skew-binary numeral systems and one application
• Thin heaps, thick heaps
• A characterization of heaps and its applications
• Two-tier relaxed heaps
• A Survey on Priority Queues
• A new heap game
• Algorithm Theory - SWAT 2004
• A note on constructing min-max heaps
• Recurrence relations on heaps
• An efficient data structure for branch-and-bound algorithm
• Heaps with bits
• On the complexity of building an interval heap
• On constant factors in comparison-based geometric algorithms and data structures
• Refined complexity analysis for heap operations
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
• Available stabilizing heaps
• Title not available (Why is that?)
• An optimal algorithm for deleting the root of a heap
• Repeated random insertion into a priority queue
• Building heaps fast
• Heap construction in the parallel comparison tree model
• QuickHeapsort: modifications and improved analysis
• An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons
• Heap construction: Optimal in both worst and average cases?
• Title not available (Why is that?)
• QuickXsort: a fast sorting scheme in theory and practice
• Best case lower bounds for heapsort
• Interval Heaps
• Optimizing binary heaps
• Sorting using heap structure
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Building heaps in parallel
• 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
• Comparator networks for binary heap construction
• Hollow Heaps

This page was built for publication: Heaps on Heaps

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