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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

возможно, это было не так, когда был задан исходный вопрос, но теперь у wiki есть ссылка на источник, и вот он: 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-й наименьший элемент.

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

Ответ 5

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

Ответ 6

Сохраните первое целое число в массиве и установите счетчик 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;
}

Ответ 7

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

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

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

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

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

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