You can actually construct the heap from unsorted data in O(n) time, so construc...

xyzzyz on Sept 14, 2021 | parent | context | favorite | on: How percentile approximation works and why it's mo...

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.

eru on Sept 15, 2021 [–]

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