Чтобы найти медиану несортированного массива, мы можем сделать минимальную кучу за O (nlogn) времени для n элементов, а затем мы можем извлечь один за другим n / 2 элемента, чтобы получить медиану. Но этот подход занял бы O (nlogn) время.

Можем ли мы сделать то же самое некоторым способом за O (n) раз? Если мы можем, пожалуйста, скажите или предложите какой-нибудь метод.