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

Question

Википедия говорит:

Алгоритмы выбора: нахождение мин, max, как min, так и max, медиана или даже k-й по величине элемент может быть сделано за линейное время с использованием куч.

Все, что он говорит, это то, что это можно сделать, а не как.

Можете ли вы дать мне некоторое представление о том, как это можно сделать с помощью кучи?

Answer 1

Вы бы использовали кучу мин-макс-медиана, чтобы найти мин, макс и медиану в постоянное время (и потратить линейное время для построения кучи). Вы можете использовать деревья статистики заказов, чтобы найти kth наименьшее / наибольшее значение. Обе эти структуры данных описаны в этой статье о кучах min-max [pdf link] . Кучи Min-Max - это двоичные кучи, которые чередуются между min-heaps и max-heaps.

Из статьи: min-max-median heap - это двоичная куча со следующими свойствами:

1) Медиана всех элементов находится в корне

2) Левое поддерево корня представляет собой минимально-максимальную кучу Hl потолка размера [((n-1) / 2)], содержащую элементы, меньшие или равные медиане. Правое поддерево - это максимальная куча Hr размера пола [((n-1) / 2)], содержащая только элементы, большие или равные медиане.

В статье объясняется, как построить такую ​​кучу.

Редактировать: После более тщательного прочтения статьи создается впечатление, что для построения кучи min-max-median необходимо сначала найти медиану (FTA: «Найти медиану всех n элементов с использованием любого из известных линейных значений времени). алгоритмы "). Тем не менее, после того, как вы построили кучу, вы можете поддерживать медиану, просто поддерживая баланс между кучей min-max слева и кучей max-min справа. DeleteMedian заменяет корень либо на минимальную кучу max-min, либо на максимальную кучу min-max (в зависимости от того, какой баланс поддерживается).

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

Answer 2

Вероятно, есть лучшие алгоритмы, но вот как я это сделаю:

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

Answer 3

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

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

Answer 4

возможно, это было не так, когда был задан оригинальный вопрос, но теперь в вики есть ссылка на источник, и вот оно: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf

, в частности, перейдите на страницу 17 и посмотрите описание RSEL4. В теореме 3.2 они доказывают, что временная сложность этого k-го алгоритма выбора равна O (k). так что вам понадобится O (n), чтобы построить кучу, и дополнительный O (k), чтобы найти k-й самый маленький предмет.

это не так просто, как предлагали некоторые другие ответы

Answer 5

Сохраните первое целое число в массиве и установите счетчик на 1. Затем выполните цикл по оставшимся целым числам в векторе. Если текущее целое число в массиве совпадает с сохраненным, счетчик увеличивается на единицу, в противном случае счетчик уменьшается на единицу. Если счетчик когда-либо достигнет нуля, отбросьте сохраненное целое число и замените его текущим целым числом в массиве. Когда вы, наконец, перебрали все целые числа, у вас остался один кандидат. Затем вам нужно снова пройтись по массиву и посчитать вхождение кандидата, чтобы убедиться, что это действительно доминирующий элемент.

static int FindDominator(int[] arr)
{
int counter = 1;
int candidate = arr[0];
for(int i = 1; i < n; i++)
{
   if(arr[i] == candidate) counter++
    else 
   {
        counter--;
        if(counter == 0) { candidate = arr[i]; counter = 1; }
    }
}
counter = 0;
for(int i = 0;  i < n; i++)
{
    if(arr[i] == candidate) counter++;
}
if(counter > n / 2) return candidate;
else return -1;
}

Answer 6

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

Answer 7

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

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

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

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

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

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