On the random construction of heaps

DOI10.1016/0020-0190(88)90101-9zbMATH Open0654.68026OpenAlexW1984625335WikidataQ57401618 ScholiaQ57401618MaRDI QIDQ1108784FDOQ1108784

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

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?

zbMATH Keywords

upper boundbinary heapd-heaps

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Repeated random insertion into a priority queue

Cited In (14)

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

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)