Как я нахожу медиану чисел в линейное время с помощью "кучи"?

Очевидно, что min и max в O (n) просты и не требуют кучи.

K-й по величине можно сделать довольно просто, поддерживая до сих пор кучу k-го максимального значения. Время выполнения будет O (n * logk). Вы могли бы назвать это линейным временем, если k имеет фиксированный размер и k << n.

Я не думаю, что медиана возможна. Простое создание кучи размером O (n) требует времени O (n * logn).

Edit: Хорошо, подумав еще немного, IVlad прав.Вы можете создать кучу за O (n) для фиксированного размера. Но ... это не помогает ОП с его Медианным вопросом. Метод создания линейной кучи производит только действительную кучу в качестве конечного результата. Простой подход к выполнению n вставок, в результате чего допустимая куча после каждого шага равна O (n * logn).

Мне кажется, что использование куч для нахождения медианы потребует использования этих работающих под куч. Например, здесь был опубликован ответ (который, похоже, сейчас удален), связанный с сообщением в блоге, предлагающим алгоритм решения этой проблемы. Он отслеживал текущую медиану, используя две кучи (меньшую половину и большую половину), поскольку он выполняет один проход через данные. Это потребует более медленного и наивного подхода к куче, потому что он зависит от поддержания действительных куч при вставке и удалении из них.

Есть ли другой способ найти медианное значение, используя метод линейного однократного создания кучи?

Вероятно, существуют более эффективные алгоритмы, но я бы сделал это следующим образом:

Имейте два сегмента и значение. Значение - это медиана, два сегмента «больше медианы» и «меньше медианы».Для каждого элемента x в массиве перебалансируйте сегменты таким образом, чтобы big_bucket и small_bucket различались по размеру не более чем на 1. При перемещении элементов из большого ведра в маленькое они сначала должны пройти через медианное значение, чтобы попасть туда (то есть, разница в 2 приведет к успешному перемещению элемента из одного ведра в другое, а при разнице в 1 элемент будет выталкиваться. от одного ведра до среднего значения.) В конце вашего первого прохода по массиву значение должно быть вашим медианным значением.

См. Эту страницу в Википедии об алгоритмах выбора . В частности, посмотрите на алгоритм BFPRT и алгоритм медианы медиан. BFPRT является вероятностно линейным и моделируется на основе быстрой сортировки; Медиана медиан гарантированно линейна, но имеет большой постоянный коэффициент, поэтому на практике может потребоваться больше времени, в зависимости от размера вашего набора данных.

Если у вас есть всего несколько сотен или тысяч элементов, из которых можно выбрать медиану, я подозреваю, что простая быстрая сортировка с последующим прямым индексированием проще всего.

Если вы знаете больше о структуре данных кучи, вы легко поймете, что это действительно так. Структура кучи может быть построена за O (n) раз, есть минимальная куча и максимальная куча. Минимальный корневой элемент кучи даст вам наименьший элемент. Максимальный корневой элемент кучи даст вам максимальный элемент. Просто построив кучу, вы найдете минимальное и максимальное значение. та же идея для медианы и k-го наибольшего, при построении кучи вы можете найти медиану и k-е наибольшее, глядя на левую или правую ветвь дерева и сохраняя постоянный объем памяти для хранения номера элемента. и т. д.