On the random construction of heaps

DOI10.1016/0020-0190(88)90101-9MaRDI QIDQ1108784zbMATH OpenOpenAlexWikidataFDO

Authors Alan Frieze

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90101-9

zbMATH Keywords

upper boundbinary heapd-heaps

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Algorithms in computer science (68W99)

Recommendations

• Building heaps fast
• scientific article; zbMATH DE number 1984550
• Average case analysis of heap building by repeated insertion
• An average case analysis of Floyd's algorithm to construct heaps
• Heap construction: Optimal in both worst and average cases?

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Probability Inequalities for Sums of Bounded Random Variables
• Repeated random insertion into a priority queue

Cited in

(14)

• Average case analysis of heap building by repeated insertion
• A note on the problem of heaps
• Asymptotic behavior in a heap model with two pieces
• A cut-invariant law of large numbers for random heaps
• Best case lower bounds for heapsort
• Expected heights in heaps
• Heap construction: Optimal in both worst and average cases?
• An average case analysis of Floyd's algorithm to construct heaps
• A note on constructing binary heaps with periodic networks.
• A note on constructing min-max heaps
• Recurrence relations on heaps
• Almost-sure asymptotics for the number of heaps inside a random sequence
• scientific article; zbMATH DE number 1543353 (Why is no real title available?)
• scientific article; zbMATH DE number 1984550 (Why is no real title available?)

This page was built for publication: On the random construction of heaps

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