Comment by eru

I have a similar story about an interesting little advance in computing that I haven't formally published anywhere, but it's at https://cs.stackexchange.com/a/171695/50292

The question boils down to: can you simulate the bulk outcome of a sequence of priority queue operations (insert and delete-minimum) in linear time, or is O(n log n) necessary. Surprisingly, linear time is possible.