Hacker News new | past | comments | ask | show | jobs | submit login

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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: