A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm

DOI10.1007/978-1-4614-5134-1_10MaRDI QIDQ4596160zbMATH OpenOpenAlexFDO

Authors Ioannis Paparrizos

Publication date 30 November 2017

Published in Optimization Theory, Decision Making, and Operations Research Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.0956

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms (68W40)

Abstract: In this paper a tight bound on the worst-case number of comparisons for Floyd's well known heap construction algorithm, is derived. It is shown that at most 2n-2{mu}(n)-{sigma}(n) comparisons are executed in the worst case, where {mu}(n) is the number of ones and {sigma}(n) is the number of zeros after the last one in the binary representation of the number of keys n.

Recommendations

• Elementary yet precise worst-case analysis of Floyd's heap-construction program
• Heap construction: Optimal in both worst and average cases?
• Algorithms and Data Structures
• Building heaps fast
• An average case analysis of Floyd's algorithm to construct heaps

Cites work

• A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
• Algorithm design: Foundations, analysis, and Internet examples
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• Introduction to algorithms
• The Analysis of Heapsort

Cited in

(8)

• The bounds of min-max pair heap construction
• Elementary yet precise worst-case analysis of Floyd's heap-construction program
• An average case analysis of Floyd's algorithm to construct heaps
• The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items
• A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm
• Algorithms and Data Structures
• Heap construction: Optimal in both worst and average cases?
• The derivation of a tighter bound for top-down skew heaps

This page was built for publication: A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm

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