Heaps on Heaps

DOI10.1137/0215068MaRDI QIDQ3756520zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexity of comparison based problemslower boundspriority queue operations on a heap

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(44)

• A note on constructing min-max heaps
• Best case lower bounds for heapsort
• On the complexity of building an interval heap
• Heaps and heapsort on secondary storage
• A new heap game
• Comparator networks for binary heap construction
• Available stabilizing heaps
• Recurrence relations on heaps
• QuickXsort: a fast sorting scheme in theory and practice
• On constant factors in comparison-based geometric algorithms and data structures
• Optimizing binary heaps
• On the ``heap problem
• Sorting using heap structure
• A survey on priority queues
• An in-place heapsort algorithm requiringnlogn+nlog*n−0.546871ncomparisons
• scientific article; zbMATH DE number 4014031 (Why is no real title available?)
• An in-place priority queue with O(1) time for push and n + O(1) comparisons for pop
• Hollow Heaps
• Repeated random insertion into a priority queue
• scientific article; zbMATH DE number 4047086 (Why is no real title available?)
• Weak heaps engineered
• Merging heaps in parallel
• scientific article; zbMATH DE number 140493 (Why is no real title available?)
• Interval Heaps
• Optimal algorithms for inserting a random element into a random heap
• scientific article; zbMATH DE number 1555945 (Why is no real title available?)
• Building heaps fast
• scientific article; zbMATH DE number 742986 (Why is no real title available?)
• A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort
• Thin heaps, thick heaps
• Heap construction in the parallel comparison tree model
• Parallel combining: benefits of explicit synchronization
• Algorithm Theory - SWAT 2004
• An efficient data structure for branch-and-bound algorithm
• Refined complexity analysis for heap operations
• Cascade heap: towards time-optimal extractions
• Heap construction: Optimal in both worst and average cases?
• Heaps with bits
• Two skew-binary numeral systems and one application
• An optimal algorithm for deleting the root of a heap
• Building heaps in parallel
• A characterization of heaps and its applications
• Two-tier relaxed heaps
• Parallel heap: an optimal parallel priority queue

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)