Talk:Binary heap

This is the first time I have seen an average case analysis of the binary heap operations, and it is very helpful to know what they are since it shows that in practical real-world applications, it is probably better than many other structures mainly because of the low constants involved. Plus, the average case analysis helps analyze the average case running time of other algorithms that use the binary-heap as an auxiliary data structure.

UPDATE: The analysis of the expected number of swaps used when adding an element is incorrect. It assumes a uniform distribution of keys, but keys are certainly not uniformly distributed in a heap. In a min-heap, smaller keys are far more likely to be near the top, etc. Empirically, an average of approximately 1.281 swaps per add.