Cbcomp

Heap average insertion

Hello, and thanks for your contribution to Binary heap. I was earlier skeptical about the avg. insertion time, but it seems I had erred. The paper is a great find, although I am no wiser about the maths, but at least it seems to indeed prove O(1) for avg. insertion. I did empirical tests, like the ones you described, and I was unable to make the heap size (n) have any kind of effect on measured avg. insertion time complexity. The measured ops/insert over a large sample (10,000 random inserts to a heap of n random values) was always around 2–3, from inserting to heap of n=1,000 all the way to n=100,000,000 (any larger values caused core dump due to running out of RAM). Seems like the effect n can have on avg. ops required per insertion is indeed bound by a constant, like the paper claims. --hydrox (talk) 06:44, 1 February 2014 (UTC)