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

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

Из бумаги:

Мин-макс-медианная куча — это бинарное дерево со следующими свойствами:

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

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

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

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

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

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

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

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

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

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

Это не так просто, как предполагалось в некоторых других ответах.

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

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

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

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

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

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

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

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