Heapsort with your hollow-heap implementation looks to be O(n^2)

[adtac]

Hi, I was implementing hollow heap myself and stumbled upon your implementation when I was searching for other implementations to benchmark my code against.

I wrote a simple benchmarking application to generate N random numbers (in the range [0, N)) and push them into the heap one-by-one. Then I call delete-min N times, noting the find-min result before each delete. This should produce a sorted list in O(N log N).

However your implementation produced a O(N^2)-like graph when I graphed the time taken vs N. See below:

^ x-axis is N, y-axis is time to heapsort in microseconds

The red heap is my implementation, blue is boost's fibonacci heap, and green is your heap. Both red and blue are O(N log N)-ish, but yours is O(N^2)-ish. I verified that the output of all three heapsorts is properly sorted. I'm not sure where the inefficiency is but I thought I should just let you know.

(My hollow heap implementation: src)