Repeated random insertion into a priority queue |
| |
| Authors: | Bla Bollobs Istvan Simon |
| |
| Institution: | Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803 USA;Instituto de Matemática, Estatística e Ciência da Computação, Universidade de Campinas, Caixa Postal 6155, 13.100 Campinas, SP, Brasil |
| |
| Abstract: | The average cost of inserting n elements into an initially empty heap is analyzed, under the assumption that the n! orders in which the n elements can be inserted are equally likely. It is proved that this average, expressed in number of exchanges per insertion, is bounded by a constant about 1.7645. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
