On the random construction of heaps
type: Item
instance of: scholarly article
title: On the random construction of heaps
zbMATH Open document ID: 0654.68026
DOI: 10.1016/0020-0190(88)90101-9
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: We give a simple proof of the result of \textit{B. Bollobás} and \textit{I. Simon} [J. Algorithms 6, 466-477 (1985; Zbl 0592.68022)] on the linear expected time construction of a binary heap. We also give bounds on the probability that the construction time is much more than this and generalize the result to d-heaps, \(d\geq 2\).
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 4068256
zbMATH Keywords: upper bound
zbMATH Keywords: binary heap
zbMATH Keywords: d-heaps
Wikidata QID: Q57401618
author: Alan Frieze
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90101-9
OpenAlex ID: W1984625335
cites work: Repeated random insertion into a priority queue
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Q4057549
description: scientific article; zbMATH DE number 4068256