You can actually construct the heap from unsorted data in O(n) time, so constructing the heap is definitely not sorting. However, yeah, to actually use the heap to find median in O(n) time, you need to do something similar to magic-five (median of medians) algorithm.

Something like QuickSelect is probably better in practice than median-of-medians.

> but "huge" means "more than you can store"

Really? Where's it coming from?

I think they mean having more than you can store simultaneously on a single device.

With a few exceptions this is pretty common scenario.

More than you can store.

And possibly it's live data.