найти медиану несортированного массива с использованием кучи

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


median binary-heap
person noOne    schedule 04.08.2019    source источник
comment
stackoverflow.com/a/5970314/10396   -  person AShelly    schedule 16.08.2019

Ответы (1)


arrow_upward
1
arrow_downward

Хитрость здесь заключается в использовании двух куч, одна из которых является минимальной кучей, а другая — максимальной кучей. Не буду вдаваться в подробности, но для реализации требуемого алгоритма достаточно следующих пунктов.

  1. Вершина минимальной кучи — это наименьший элемент, больший или равный среднему значению.
  2. Вершина максимальной кучи — это самый большой элемент, меньший или равный среднему значению.

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

Если вы хотите вычислить медиану всех элементов массива только один раз, то сортировка будет хорошей идеей.

Надеюсь это поможет.

person sanketd617    schedule 04.08.2019