On the random construction of heaps (Q1108784): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q57401618, #quickstatements; #temporary_batch_1707303357582 |
||
| Property / Wikidata QID | |||
| Property / Wikidata QID: Q57401618 / rank | |||
Normal rank | |||
Revision as of 14:12, 7 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the random construction of heaps |
scientific article |
Statements
On the random construction of heaps (English)
0 references
1988
0 references
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\).
0 references
upper bound
0 references
binary heap
0 references
d-heaps
0 references
