On the random construction of heaps (Q1108784)

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\).