5 ms·
No, for 2 reasons, 1. huge data set: heaps requires storing the whole set, but "huge" means "more than you can store" 2. without sorting it: heaps are basical
by tantalor 5y ago
No, for 2 reasons,
1. huge data set: heaps requires storing the whole set, but "huge" means "more than you can store"
2. without sorting it: heaps are basically semi-sorted, so you are breaking the rules
- xyzzyz 5y agoYou 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.
- eru 5y agoSomething like QuickSelect is probably better in practice than median-of-medians.
- thaumasiotes 5y ago> but "huge" means "more than you can store" Really? Where's it coming from?
- namrog84 5y agoI think they mean having more than you can store simultaneously on a single device. With a few exceptions this is pretty common scenario.
- Dylan16807 5y agoMore than you can store. And possibly it's live data.