AN AVERAGE CASE ANALYSIS OF FLOYD ALGORITHM TO CONSTRUCT HEAPS

作     者：DOBERKAT, EE 

作者机构：Department of Mathematics and Computer Science Clarkson College of Technology Potsdam New York 13676 USA 

出 版 物：《INFORMATION AND CONTROL》 (Inf Control)

年 卷 期：1984年第61卷第2期

页      面：114-131页

核心收录：

基　　金：United States Energy Research and Development Administration, (E(11-1)-3070) National Aeronautics and Space Administration, NASA, (NSG 1323) National Aeronautics and Space Administration, NASA Massachusetts Institute of Technology, MIT 

主　　题：COMPUTER PROGRAMMING 

摘      要：The expected number of interchanges and comparisons in Floyd s well-known algorithm to construct heaps and derive the probability generating functions for these quantities are considered. From these functions the corresponding expected values are computed.