Дан массив [1;n]
— содержащий n целых числел (32 битных integer);
— массив НЕ отсортирован;
— в массиве есть дубликаты;

Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
Т.е. в массиве {1,2,3,3,4} при k=3 ответ будет 2,3,4 а не 3,3,4.

Идеи:
1. Quicksort O(nlogn). Избавляемся от дубликатов O(n).
Время растет пропорционально O(nlogn) — не интересно.
2. Heapsort — тоже самое еще хуже.
Составляем max-heapsort что называется in-place переставлением элементов в массиве и просеиванием вверх.
Уже O(nlogn). Плюс вывод первых максимальных чисел O(klogn) — не интересно.
В инете читал разговоры про составление maxheap inplace за O(n) но не дошло пока (мало образования может кто сможет пояснить есть такое или нет?
Не понятно: как выкидывать дубликаты.
3. Counting sort используя bit-вектор — O(n) — уже интереснее.
Плюсы: Битвектор сожрет O(2^32/8) байт памяти или 536 мегов — что уже не интересно. Отпадает.
Плюс: отличная борьба с дубликатами за тот же самый проход.
4. Алгоритм поиска Хоара "Divide and Conquer" (тот что и про поиск медианы) — O(n) все круто, но отпадает.
Потому что он эффективен для поска k-первых максимальных/минимальных чисел в массиве с _уникальными_ числами. У нас же массив содержит дубликаты. Поэтому применив поиск k-первых максимальных чисел мы получим ответ с дубликатами, нам же надо без дубликатов. Отпадает?

Какие еще могут быть идеи за O(n) и память O(1).

Здравствуйте, PaulMinelly, Вы писали:

PM>Дан массив [1;n]
PM>- содержащий n целых числел (32 битных integer);
PM>- массив НЕ отсортирован;
PM>- в массиве есть дубликаты;

PM>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
PM>Т.е. в массиве {1,2,3,3,4} при k=3 ответ будет 2,3,4 а не 3,3,4.
Такой, намного странный вопрос, если я положу k == N, то что мы одидаем? Отсортированный за O(N) массив?

Ещё другой странный вопрос. А если у меня не найдётся k разных чисел в массиве, то что делаем?

В любом случае, если мы типа фиксируем k и увеличиваем только N, то тогда O( N ), то можно, IMHO, решать "в лоб", так как k -- константа...

Если известно, что k<<N, то куча вполне подойдет (Ее можно создать линейно).

Еще ты не указал, важно ли выдавать результат отсортированным.

PM>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).

Нужно использовать поделенный на куски битовый вектор. Пусть у нас всего возможных значений чисел 2^32. Мы берем и делим эти значения на 2^16 групп по 2^16 значений. Из этих групп держим в памяти те, которые содержать k самых больших чисел. А если k мало, то можно хранить k групп с самыми большими значениями и не париться. Время: O(N). Недостатки: не имеет смысла использовать при больших k. В последнем случае можно воспользоваться поразрядной сортировкой.

Здравствуйте, PaulMinelly, Вы писали:

PM>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
PM>Т.е. в массиве {1,2,3,3,4} при k=3 ответ будет 2,3,4 а не 3,3,4.
k максимальных значений — слово первых лишнее

PM>Какие еще могут быть идеи за O(n) и память O(1).
одно максимальное находится за O(n), заменяем его за O(n) на минимальное и так к раз. K<<N значит K=O(1).
Можно конечно и побыстрей только это циклы писать, алгоритмами СТЛ не получится

Здравствуйте, PaulMinelly, Вы писали:

PM>Какие еще могут быть идеи за O(n) и память O(1).
Загнать данные в Judy array и взять k старших

E>Такой, намного странный вопрос, если я положу k == N, то что мы одидаем? Отсортированный за O(N) массив?

Нет, сортировать выходной массив не надо. Просто вывести k-максимальных чисел как получится, без сортировки. Иначе, действительно получилась бы сортировка за O(n).

Здравствуйте, Pro100Oleh, Вы писали:


PO>Еще ты не указал, важно ли выдавать результат отсортированным.

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

PO>Если известно, что k<<N, то куча вполне подойдет (Ее можно создать линейно).

Да, k намного меньше чем N.
Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.

Здравствуйте, PaulMinelly, Вы писали:

[SKIPPED]

PM>Какие еще могут быть идеи за O(n) и память O(1).

Только RadixSort O(N) по времени + избавится от дубликатов очень просто.
Существуют версии RadixSort сортирующие на месте, а counting можно делать битами, поэтому потребуется совсем чуть дополнительной пямяти, причем O(1)

Здравствуйте, PaulMinelly, Вы писали:

PM>Да, k намного меньше чем N.
PM>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.
При k << N я думаю тебе должно подойти лобовое решение за O(N * k).
Находишь первое максимальное число за O(N). Запоминаешь его в список. Дальше ищешь за O(N) максимальное число, игнорируя значения массива из списка найденных значений.

Здравствуйте, vb-develop, Вы писали:

VD>Здравствуйте, PaulMinelly, Вы писали:

PM>>Да, k намного меньше чем N.
PM>>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.
VD>При k << N я думаю тебе должно подойти лобовое решение за O(N * k).
VD>Находишь первое максимальное число за O(N). Запоминаешь его в список. Дальше ищешь за O(N) максимальное число, игнорируя значения массива из списка найденных значений.
Небольшое дополнение. После каждого прохода по всему массиву можно максимальное значение заменять на MAX_INT, и при этом игнорировать значения MAX_INT начиная со второго прохода.

Здравствуйте, vb-develop, Вы писали:

VD>Здравствуйте, vb-develop, Вы писали:

VD>>Здравствуйте, PaulMinelly, Вы писали:

PM>>>Да, k намного меньше чем N.
PM>>>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.
VD>>При k << N я думаю тебе должно подойти лобовое решение за O(N * k).
VD>>Находишь первое максимальное число за O(N). Запоминаешь его в список. Дальше ищешь за O(N) максимальное число, игнорируя значения массива из списка найденных значений.
VD>Небольшое дополнение. После каждого прохода по всему массиву можно максимальное значение заменять на MAX_INT, и при этом игнорировать значения MAX_INT начиная со второго прохода.

Это решение теоритически не самое крутое. Но все равно спасибо.

Здравствуйте, PaulMinelly, Вы писали:



а где тут этюд?!
более подходящий форум имхо — алгритмы

Здравствуйте, PaulMinelly, Вы писали:

PM>2. Heapsort — тоже самое еще хуже.
PM>Составляем max-heapsort что называется in-place переставлением элементов в массиве и просеиванием вверх.
PM>Уже O(nlogn). Плюс вывод первых максимальных чисел O(klogn) — не интересно.

Э, почему nlogn?
Создаём приоритетную очередь с минимумом в голове, длиной не более k.
Скармливаем туда массив; при переполнении выбрасываем голову. Это nlogk в чистом виде.

Причём замечу, что можно очередь сделать на пирамиде, а можно на балансируемом двоичном дереве (только это уже не inplace).
В последнем случае мы очень просто поборемся с дубликатами.

set<int> stats;
for(it=begin; it!=end; ++it)
{
    stats.insert(*it);
    if(stats.size()==k+1)
        stats.erase(stats.begin());
}

DB>Здравствуйте, PaulMinelly, Вы писали:

DB>а где тут этюд?!
DB>более подходящий форум имхо — алгритмы

Да, этюда нет, надо бы передвинуть в алгоритмы. Не туда нажал, сорри

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, PaulMinelly, Вы писали:

PM>>2. Heapsort — тоже самое еще хуже.
PM>>Составляем max-heapsort что называется in-place переставлением элементов в массиве и просеиванием вверх.
PM>>Уже O(nlogn). Плюс вывод первых максимальных чисел O(klogn) — не интересно.

К>Э, почему nlogn?
К>Создаём приоритетную очередь с минимумом в голове, длиной не более k.
К>Скармливаем туда массив; при переполнении выбрасываем голову. Это nlogk в чистом виде.

К>Причём замечу, что можно очередь сделать на пирамиде, а можно на балансируемом двоичном дереве (только это уже не inplace).

Клево! Только пара вопросов.
Если строить приоритетную очередь на пирамиде — это имеется ввиду на куче?
Кучу можно построить на дополнительном массиве размера k — все здорово.
Только не понятно как можно отбрасывать голову у кучи. Ведь тогда последний элемент ставить в голову и просеивать вниз что занимает logk. Получается что кол-во вставок будет n каждая вставка — это logk просеиваний в куче. И того мы имеем nlogk.
Я правильно все прикинул? Там же в куче можно бороться с дубликатами сразу же.

Здравствуйте, PaulMinelly, Вы писали:

PM>Клево! Только пара вопросов.
PM>Если строить приоритетную очередь на пирамиде — это имеется ввиду на куче?

По-русски эту структуру (binary heap) иногда называют пирамидой. А сортировку, соответственно, пирамидальной.

PM>Кучу можно построить на дополнительном массиве размера k — все здорово.

А зачем на дополнительном? Просто скармливаем первые k элементов массива, и на их месте по ходу скармливания вырастает куча.
С учётом отбрасывания дубликатов, её размер может быть меньше k, ну и ладно — главное, что не больше.

Хотя если исходный массив жалко портить — то пусть будет дополнительный.

PM>Только не понятно как можно отбрасывать голову у кучи. Ведь тогда последний элемент ставить в голову и просеивать вниз что занимает logk. Получается что кол-во вставок будет n каждая вставка — это logk просеиваний в куче. И того мы имеем nlogk.

Именно это я и имел в виду. Что nlogk, а не nlogn.

PM>Я правильно все прикинул? Там же в куче можно бороться с дубликатами сразу же.

А вот тут меня сомнения обуяли — можно ли в куче эффективно бороться с дубликатами. Ведь она не обеспечивает строгий порядок.
Вот смотри: начали строить кучу из серии a,b,c,d,e.

a
| \
b  c
|\  \
d e

Добавляем ещё одну d или e. В ветку b она не попадёт, поэтому про дубликаты мы не узнаем.

Здравствуйте, PaulMinelly, Вы писали:

DB>>а где тут этюд?!
DB>>более подходящий форум имхо — алгритмы

PM>Да, этюда нет, надо бы передвинуть в алгоритмы. Не туда нажал, сорри

Как раз этюд.
Дайте народу поразмять извилину.
Решений-то много.

Кстати, функциональщики могут попрововать на иммутабельных структурах с последовательным доступом.
А хаскельщики — слабо на ленивом массиве?

Здравствуйте, PaulMinelly, Вы писали:

PM>Какие еще могут быть идеи за O(n) и память O(1).

top-heapsort (куча размера k):

занос в кучу — C
проход по массиву с занесением в кучу O(n)
расход памяти O(1)

после прохода в куче искомый ответ.

Здравствуйте, Аноним, Вы писали:

А>занос в кучу — C
А>проход по массиву с занесением в кучу O(n)
А>расход памяти O(1)

А>после прохода в куче искомый ответ.
Не совсем... у тебя будет ответ с дубликатами...

Кроме того, если уж ты считаешь, что k -- это константа, то можно и попроще.
Заводишь просто массив из k элементов, ну и заполняешь его по мере просмотра большого массива...
Тоже O(N) получается...

Тоже не совсем. Отвечу обоим сразу.

А>>занос в кучу — C
Могли бы Вы рассказать как это занос в кучу С? С — это константа?
Занос в кучу это logk для каждого элемента. Это будет делаться так: удаляем голову, ставим на ее место новый элемент и просеиваем вниз. Просеивание куда угодно — это O(logk).
Поэтому если у нас встретится массив такой что каждый новый элемент будет больше предыдущего (худший случай) — это потребует занос каждого нового элемента в кучу и выкидывание минимального — и это уже будет nlogk — общий случай. Откуда взялось C для заноса в кучу?

E>Кроме того, если уж ты считаешь, что k -- это константа, то можно и попроще.
E>Заводишь просто массив из k элементов, ну и заполняешь его по мере просмотра большого массива...

И второму автору — увы, O(n) не получается.
Допустим мы заполнили наш новый k-массив первыми элементами. Отлично. Теперь есть два момента:
1. Надо убирать дубликаты на каждом шаге.
Если на массиве у нас нет кучи — то тогда придется просматривать вcе k-элементов (sequential search) чтобы решить булет новый элемент дубликатом или нет. Это O(k).
2. Опять же если на массиве нет кучи — то при добавлении нового элемента мы должны найти последовательным поиском минимальный элемент и заменить на новый. Поиск минимального — это O(k) опять.
И это надо делать для каждого из n элементов. Итог: O(n*2*k) или O(nk).

E>Тоже O(N) получается...

Нет. Получается O(nk), что хуже против алгоритма с кучей сложность которого O(nlogk) — оно намного ниже.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, PaulMinelly, Вы писали:

DB>>>а где тут этюд?!
DB>>>более подходящий форум имхо — алгритмы

PM>>Да, этюда нет, надо бы передвинуть в алгоритмы. Не туда нажал, сорри

К>Как раз этюд.
К>Дайте народу поразмять извилину.
К>Решений-то много.

Какие решения еще решения Вы считаете правильными? Остальные посмотрел — не совсем понял. Круче nlogk — ничего не нашел. Radix sort — даст O(nk) — что является хуже алгоритма с кучей. Плюс избавление от дубликатов не понятно как.
Какие варианты из написанных Вы бы выделили особо? Я пытался над ними думать, но все не доходит до меня как можно еще извернуться за nlogk или ниже если не использовать кучу.

А если брать кучу размером k такую, что в голове находится наименьший элемент? Тогда будет сразу ясно, нужно ли добавлять очередной элемент.

Здравствуйте, PaulMinelly, Вы писали:

PM>Какие решения еще решения Вы считаете правильными? Остальные посмотрел — не совсем понял. Круче nlogk — ничего не нашел. Radix sort — даст O(nk) — что является хуже алгоритма с кучей. Плюс избавление от дубликатов не понятно как.

Радикс — O(nb), где b — разрядность.
Если b < logk, то выигрыш будет. Плюс, опять же, разные константы скорости — нужно смотреть, там с кешем может чёрти-что твориться, а может и не твориться.

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

PM>Какие варианты из написанных Вы бы выделили особо? Я пытался над ними думать, но все не доходит до меня как можно еще извернуться за nlogk или ниже если не использовать кучу.

1) Полная сортировка, затем берём первые k уникальных.

Быстрые сортировки (quick для массивов, merge для списков) — O(nlogn), на самом деле если logk сравним с logn, то не жалко и отсортировать.
Радикс — O(n*b).
Сортировка подсчётом — O(n+r) времени и O(r) памяти (битовый вектор) — где r — диапазон значений (logr = b).

Да, не забываем, что радикс и подсчёт применимы только для чисел с натуральным порядком. Для произвольного отношения порядка (в т.ч. над произвольными объектами — вещественные числа, строки) фокус не пройдёт.

2) Частичная сортировка.

Модификация частичной быстрой сортировки std::partial_sort — нужно параллельно подсчитывать число уникальных элементов (и выбрасывать их) и при необходимости досортировывать то, что оказалось после медианы. Обычный алгоритм подсчитывает число элементов вообще.
O(nlogk), наверное. Хотя надо подумать.

Модификация пирамидальной сортировки: упаковываем n, распаковываем первые k уникальных. O(nlogn) — нда, неприятно.

Очередь с приоритетами (поверх двоичного дерева, а не поверх пирамиды) — O(nlogk). Если дерево ещё и разместить в цельном блоке памяти, то кэш не будем насиловать.


Итак, выбираем из nlogk, nlogr, n+r.
По-моему, неплохой ассортимент.

Здравствуйте, PaulMinelly, Вы писали:


E>>Тоже O(N) получается...
PM>Нет. Получается O(nk), что хуже против алгоритма с кучей сложность которого O(nlogk) — оно намного ниже.
Это всё не понятно как считают. Типа нужен алгоритм, не зависящий от K, или зависимость от K не интересует?
Если второе, то понятно, например, почему занесение в кучу константа...

Здравствуйте, Roman Odaisky, Вы писали:

RO>А если брать кучу размером k такую, что в голове находится наименьший элемент? Тогда будет сразу ясно, нужно ли добавлять очередной элемент.

На самом деле можно иметь две кучи, и иметь ссылки между ними.
Тогда всегда можно будет знать кого выбрасывать и кого добавлять. Но что делать с дубликатами всё равно не понятно

Здравствуйте, PaulMinelly, Вы писали:

PM>4. Алгоритм поиска Хоара "Divide and Conquer" (тот что и про поиск медианы) — O(n) все круто, но отпадает.
PM>Потому что он эффективен для поска k-первых максимальных/минимальных чисел в массиве с _уникальными_ числами. У нас же массив содержит дубликаты. Поэтому применив поиск k-первых максимальных чисел мы получим ответ с дубликатами, нам же надо без дубликатов. Отпадает?

Не совсем. Забрасываем сначала все числа в хэш-таблицу, избавляясь от дубликатов. Это будет O(n) c использованием O(n) памяти. Затем используем алгоритм выше, это еще раз O(n).

PM>Какие еще могут быть идеи за O(n) и память O(1).

С O(1) памятью пока как-то идей нет.

Здравствуйте, Roman Odaisky, Вы писали:

RO>А если брать кучу размером k такую, что в голове находится наименьший элемент? Тогда будет сразу ясно, нужно ли добавлять очередной элемент.

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

К>А вот тут меня сомнения обуяли — можно ли в куче эффективно бороться с дубликатами. Ведь она не обеспечивает строгий порядок.
К>Вот смотри: начали строить кучу из серии a,b,c,d,e.
К>Добавляем ещё одну d или e. В ветку b она не попадёт, поэтому про дубликаты мы не узнаем.

Задумался тоже как выкидывать дубликаты из кучи. Возьмем пример кучи на числах

2
| \
5  9
|\  \
10 20

Мы вытащили еще один элемент со значением 10 из массива и хотим проверить надо ли вставлять его в кучу (есть ли там уже такой или еще нет). Поскольку у нас это minheap, то действия такие:
1. Выкидываем голову (2) и ставим 10 на место головы:

10
| \
5  9
|\  \
10 20

2. Просеиваем 10 вниз (это O(logk)) начиная обсматривать с левой ветки. Получаем:
К>

К>5
К>| \
К>10  9
К>|\  \
К>10 20 
К>

3. Видим что след.-левый элемент у нас 10 — значит дубликат есть, в кучу вставлять наш элемент не надо было. Что делаем?
Вертаем все назад. Это опять O(logk). Для этого надо где-то сохранять голову, чтобы ее не выкидывать совсем.
Допустим массив у нас содержит первые k-уникальных значений, а потом все дубликаты.
Хотя тогда общая сложность все равно будет O(n*2*logk) или O(n*logk). Фу, я уж подумал что и этого решения нет

Здравствуйте, PaulMinelly, Вы писали:

PM>Мы вытащили еще один элемент со значением 10 из массива и хотим проверить надо ли вставлять его в кучу (есть ли там уже такой или еще нет). Поскольку у нас это minheap, то действия такие:
PM>1. Выкидываем голову (2) и ставим 10 на место головы:
PM>

PM>10
PM>| \
PM>5  9
PM>|\  \
PM>10 20 
PM>

PM>2. Просеиваем 10 вниз (это O(logk)) начиная обсматривать с левой ветки. Получаем:
К>>

К>>5
К>>| \
К>>10  9
К>>|\  \
К>>10 20 
К>>

И почему с левой? А если 10 будет в правой?

PM>3. Видим что след.-левый элемент у нас 10 — значит дубликат есть, в кучу вставлять наш элемент не надо было. Что делаем?
PM>Вертаем все назад. Это опять O(logk). Для этого надо где-то сохранять голову, чтобы ее не выкидывать совсем.

Это все — фантазии, куча не предназначена для поиска. Сложность поиска в куче O(n).

PM>Допустим массив у нас содержит первые k-уникальных значений, а потом все дубликаты.
PM>Хотя тогда общая сложность все равно будет O(n*2*logk) или O(n*logk). Фу, я уж подумал что и этого решения нет

Здравствуйте, PaulMinelly, Вы писали:

PO>>Если известно, что k<<N, то куча вполне подойдет (Ее можно создать линейно).

PM>Да, k намного меньше чем N.
PM>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.

Куча создается линейно следующим образом:
Для простоты предположим, что у нас в куче 2^p-1 элементов. Теперь возьмем все элементы предпоследнего уровня ([2^(p-2), 2^(p-1)-1]), и пробуем их опустить вниз. Затем поднимаемся на уровень выше и делаем то же самое и т.д. На практике это выглядит так:

for i = length(Heap)/2-1 downto 0
  do Pulldown(i)

Теперь надо доказать, что это O(n). Каждая операция Pulldown по сложности не превосходит O(logn), но это не учитывает позицию элементов в дереве. Ведь для предпоследнего ряда, например, нужно всего по одному вызову Pulldown, а для последнего вообще никаких действий не производится. Пусть у нас высота кучи h.
1 снизу ряд: для n/2 элементов выполняется 0*n/2 операций
2 снизу ряд: для n/4 элементов выполняется 1*n/4 операций
3 снизу ряд: для n/8 элементов выполняется 2*n/8 операций
4 снизу ряд: для n/16 элементов выполняется 3*n/16 операций.
...

Получаем ряд СУММА(i*n / 2^(i+1)), где i от 0 до высоты дерева-1. Выносим n.
n*СУММА(i / 2^(i+1)) <= n*СУММА(i / 2^i) 
Расмотрим теперь бесконечный ряд СУММА(i / 2^i). Покажем, что он равен 2.
СУММА(x^k) при |x| <1 как известно равен 1/(1-x)
продифференцируем это равенство по х и умножим обе части на x.
СУММА(k*x^k) = x / (1-x)^2
Подставим теперь наш x = 1/2, получили:
СУММА(k / 2^k) = 2

Вот и получили O(n)

_DA>И почему с левой? А если 10 будет в правой?

Черт, Вы правы, кучу нельзя заполнять как я написал, она заполняется справа налево (условно). Все точно, мы не сможем найти в ней дубликаты за logn время, только за O(n). Ужос. Куча отпадает. С ней сложность O(n*(klogk)).
Что хуже если исползьвать в качестве кучи упорядоченный массив с поиском и вставкой за O(k).

Тогда общая сложность отметания дубликатов и вставки каждого элемента в обычный set будет O(nk). Так же как с radixsort. Черт, неужели куча отпадает?


PM>>3. Видим что след.-левый элемент у нас 10 — значит дубликат есть, в кучу вставлять наш элемент не надо было. Что делаем?
PM>>Вертаем все назад. Это опять O(logk). Для этого надо где-то сохранять голову, чтобы ее не выкидывать совсем.

_DA>Это все — фантазии, куча не предназначена для поиска. Сложность поиска в куче O(n).

Здравствуйте, PaulMinelly, Вы писали:

_DA>>И почему с левой? А если 10 будет в правой?

PM>Черт, Вы правы, кучу нельзя заполнять как я написал, она заполняется справа налево (условно). Все точно, мы не сможем найти в ней дубликаты за logn время, только за O(n). Ужос. Куча отпадает. С ней сложность O(n*(klogk)).
PM>Что хуже если исползьвать в качестве кучи упорядоченный массив с поиском и вставкой за O(k).

PM>Тогда общая сложность отметания дубликатов и вставки каждого элемента в обычный set будет O(nk). Так же как с radixsort. Черт, неужели куча отпадает?

Что-то у тебя все перепуталось. Во-первых, с радиксом будет O(n*b), где b — разрядность. Во-вторых, с кучей даже без избавления от повторов будет O(nlogn). Если уж очень хочется использовать кучу, то как я предлагал ниже, можно использовать сначала хэш-таблицу, чтобы за O(n) избавиться от повторов, потом за O(n) построить кучу, а потом за O(klogn) вытащить k первых чисел. Будет O(n+klogn).
А еще.. тебе не понравилось предложенное мной решение за O(n)?

_DA>Что-то у тебя все перепуталось. Во-первых, с радиксом будет O(n*b), где b — разрядность.

А, ну да. Точно Ты прав.

_DA>Во-вторых, с кучей даже без избавления от повторов будет O(nlogn). Если уж очень хочется использовать кучу, то как я предлагал ниже, можно использовать сначала хэш-таблицу, чтобы за O(n) избавиться от повторов,
_DA>потом за O(n) построить кучу

А как можно за O(n) построить кучу ? В вики тоже написано что куча строится за O(n) — но я этого понять никак не могу и рядом написано что вставка в кучу занимает O(logn). Это я тоже понять не могу ведь куча строится вставками? N-вставок, каждая logn = получаем nlogn?
Или другими словами: я понимаю куча строится так. Например мы строим min-heap на массиве. Появился новый элемент, мы добавляем его в последнюю ячейку и просеиваем вверх. На определенной позиции он останавливается. Всего уровней в куче logn (хотя их вообще-то меньше в самом начале, и больше когда мы ближе к концу). То собственно кол-во вставок в кучу (чтобы ее создать) надо будет сделать O(nlogn). Или еще можно как-то хитро за O(n)?

_DA>, а потом за O(klogn) вытащить k первых чисел. Будет O(n+klogn).
_DA>А еще.. тебе не понравилось предложенное мной решение за O(n)?

Думаю мне надо сначала разобраться как строить кучу за O(n), потом размер хеш таблицы — и тогда я смогу сказать четко Я пока ламер в хеш таблицах, как хеш-функция работает — знаю, но как хеш таблица и ее коллизии (и как они разрешаются посредством bin — это для меня туман). Если мы создадим хеш таблицу — то она займет памяти 2^32? Или нет? (По размеру нашего integer'a?) или же ровно то кол-во уникальных элементов <=n сколько у нас получится?

Здравствуйте, PaulMinelly, Вы писали:

_DA>>Что-то у тебя все перепуталось. Во-первых, с радиксом будет O(n*b), где b — разрядность.

PM>А, ну да. Точно :) Ты прав.

_DA>>Во-вторых, с кучей даже без избавления от повторов будет O(nlogn). Если уж очень хочется использовать кучу, то как я предлагал ниже, можно использовать сначала хэш-таблицу, чтобы за O(n) избавиться от повторов,
_DA>>потом за O(n) построить кучу

PM>А как можно за O(n) построить кучу ? В вики тоже написано что куча строится за O(n) — но я этого понять никак не могу и рядом написано что вставка в кучу занимает O(logn). Это я тоже понять не могу ведь куча строится вставками? N-вставок, каждая logn = получаем nlogn?
PM>Или другими словами: я понимаю куча строится так. Например мы строим min-heap на массиве. Появился новый элемент, мы добавляем его в последнюю ячейку и просеиваем вверх. На определенной позиции он останавливается. Всего уровней в куче logn (хотя их вообще-то меньше в самом начале, и больше когда мы ближе к концу). То собственно кол-во вставок в кучу (чтобы ее создать) надо будет сделать O(nlogn). Или еще можно как-то хитро за O(n)?

А ты все сообщения этого топика читаешь? :) Я же тебе уже отвечал

Автор: _DAle_
Дата: 09.05.08

по поводу построения кучи за O(n). За O(n) куча строится из массива, на его же месте.

_DA>>, а потом за O(klogn) вытащить k первых чисел. Будет O(n+klogn).
_DA>>А еще.. тебе не понравилось предложенное мной решение за O(n)?

PM>Думаю мне надо сначала разобраться как строить кучу за O(n), потом размер хеш таблицы — и тогда я смогу сказать четко :) Я пока ламер в хеш таблицах, как хеш-функция работает — знаю, но как хеш таблица и ее коллизии (и как они разрешаются посредством bin — это для меня туман). Если мы создадим хеш таблицу — то она займет памяти 2^32? Или нет? (По размеру нашего integer'a?) или же ровно то кол-во уникальных элементов <=n сколько у нас получится?

Памяти нужно будет O(n), можно даже хэширование с открытой адресацией использовать. Я так понимаю, у тебя CLR есть, там есть хорошая глава про хэш-таблицы.

Здравствуйте, _DAle_, Вы писали:

_DA>Куча создается линейно следующим образом:
_DA>Для простоты предположим, что у нас в куче 2^p-1 элементов. Теперь возьмем все элементы предпоследнего уровня ([2^(p-2), 2^(p-1)-1]), и пробуем их опустить вниз. Затем поднимаемся на уровень выше и делаем то же самое и т.д. На практике это выглядит так:

_DA>

_DA>for i = length(Heap)/2-1 downto 0
_DA>  do Pulldown(i) 
_DA>

Погоди! Ты предполагаешь, что куча УЖЕ построена, после чего начинаешь мухлевать с её уровнями.
Или ты что-то иное имеешь в виду?

В порядке догадки:
— берём массив и нарубаем его на 1-, 2-, 4-, ..., -элементные подмассивы
— из каждого подмассива делаем кучу
— выполняем слияние этих куч (поскольку они уже частично упорядочены, то слияние проходит за меньшее время, чем если бы мы растили кучу поштучно)
Так?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, _DAle_, Вы писали:

_DA>>Куча создается линейно следующим образом:
_DA>>Для простоты предположим, что у нас в куче 2^p-1 элементов. Теперь возьмем все элементы предпоследнего уровня ([2^(p-2), 2^(p-1)-1]), и пробуем их опустить вниз. Затем поднимаемся на уровень выше и делаем то же самое и т.д. На практике это выглядит так:

_DA>>

_DA>>for i = length(Heap)/2-1 downto 0
_DA>>  do Pulldown(i) 
_DA>>

К>Погоди! Ты предполагаешь, что куча УЖЕ построена, после чего начинаешь мухлевать с её уровнями.
К>Или ты что-то иное имеешь в виду?

Извиняюсь, что не совсем понятно написал. Я имею ввиду, что изначально у нас есть исходный никак не упорядоченный массив чисел, и мы in-place строим в нем кучу, последовательно с конца "опуская" ее элементы. В одной из реализаций STL это написано так:

    void _Make_heap(_RanIt _First, _RanIt _Last, _Diff *, _Ty *)
    {    // make nontrivial [_First, _Last) into a heap, using operator<
    _Diff _Bottom = _Last - _First;

    for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
        {    // reheap top half, bottom to top
        --_Hole;
        _Adjust_heap(_First, _Hole, _Bottom, _Ty(*(_First + _Hole)));
        }
    }

Здравствуйте, _DAle_, Вы писали:

PM>>Да, k намного меньше чем N.
PM>>Как создать кучу линейно? В том же самом массиве? Извлечение из кучи одного элемента будет O(logk) а всех элементов O(klogk) хотя вроде нормально.
<...>
_DA>Вот и получили O(n)

Вернее не при k << N, а при немного более сильном условии: "число элементов массива, превосходящих самое маленькое из отбираемых чисел есть o( N )"

1) Строим из массива кучу за O( N ) с наибольшим элементом в вершине
2) Добываем из кучи последовательно элементы, в порядке убывания, накапливая где-то уникальные наибольшие. Пока не наберём k наибольших уникальных.
Пусть для этого нам понадобится выбрать из кучи m элементов.
Очевидно, что сложность нашего алгоритма -- это O( N ) + O( m * ln N ), но по нашему условию m = o( N ), так что O( m ln N ) = O( N )...

_DA>>>

_DA>>>for i = length(Heap)/2-1 downto 0
_DA>>>  do Pulldown(i) 
_DA>>>

К>>Погоди! Ты предполагаешь, что куча УЖЕ построена, после чего начинаешь мухлевать с её уровнями.
К>>Или ты что-то иное имеешь в виду?

Допустим у нас уже есть массив k элементов, теперь мы хотим придать этому массиву свойство кучи, причем начинаем на нем строить кучу прямо inplace.
Начинаем пробегать массив слева на право и в левой части ЭТОГО же массива формируется куча (куча растет слева на право)- эта методика описана почти везде и классическая. Это O(klogk). Ее я понял хорошо Но как сделать тоже самое за O(k) имея тот же массив и делая тоже самое in-place (заметь в первом варианте мы тоже строим кучу на массиве и inplace но за O(klogk) — не понял.

Из того что прочитал в описании — остались вопросы:
1. Почему можно опускать предпоследний уровень в массиве? Разве это придаст свойство кучи предпоследнему уровню? Ведь у нас массив не отсортирован. Мы можем только:
— добавив элемент в конец кучи — просеить его вверх O(logk). Так мы можем сформровать кучу. На этом все наши возможности по построению кучи. Или нет?
2. Может ты имеешь ввиду когда мы строим кучу inplace в массиве k элементов, то на первом шаге у нас в куче не k, а только 1 элемент, на втором шаге — 2 элемента, потом 3, 4 ... k?
И что сложность будет сумма просеиваний: log1 + log2 + log3 + log4 + ... + logk или как? И чему сумма будет равна? lol, это какой-то амортизационный анализ?

Здравствуйте, PaulMinelly, Вы писали:

_DA>>>>for i = length(Heap)/2-1 downto 0
_DA>>>> do Pulldown(i)
_DA>>>>

К>>>Погоди! Ты предполагаешь, что куча УЖЕ построена, после чего начинаешь мухлевать с её уровнями.
К>>>Или ты что-то иное имеешь в виду?

PM>Допустим у нас уже есть массив k элементов, теперь мы хотим придать этому массиву свойство кучи, причем начинаем на нем строить кучу прямо inplace.
PM>Начинаем пробегать массив слева на право и в левой части ЭТОГО же массива формируется куча (куча растет слева на право)

Справа налево, в правой части.

PM> — эта методика описана почти везде и классическая. Это O(klogk).

Это O(n). И я вроде привел доказательство этого факта.

PM> Ее я понял хорошо :) Но как сделать тоже самое за O(k) имея тот же массив и делая тоже самое in-place (заметь в первом варианте мы тоже строим кучу на массиве и inplace но за O(klogk) — не понял.

PM>Из того что прочитал в описании — остались вопросы:
PM>1. Почему можно опускать предпоследний уровень в массиве? Разве это придаст свойство кучи предпоследнему уровню? Ведь у нас массив не отсортирован.

Опускать — это означает сравнивать с дочерними элементами и менять их местами так, чтобы выполнялось свойство кучи. То есть это та же операция, которая производится при удалении элемента, после установки последнего элемента в корень дерева. Примерно так:

while (pos*2+1 < size)
{
  newpos = pos*2+1;
  if (pos*2+2 < size && heap[pos*2+2] > heap[newpos]) newpos = pos*2+2;
  if (heap[pos] < heap[newpos])  
  {
    swap(heap[pos], heap[newpos]);
    pos = newpos;
  }
  else break;
}

Понятно, что, применив это к элементам предпоследнего ряда, у нас будет выполнятся свойство кучи для элементов предпоследнего ряда.

PM>Мы можем только:
PM>- добавив элемент в конец кучи — просеить его вверх O(logk). Так мы можем сформровать кучу. На этом все наши возможности по построению кучи. Или нет?
Нет. Я ведь и код уже привел из STL..
PM>2. Может ты имеешь ввиду когда мы строим кучу inplace в массиве k элементов, то на первом шаге у нас в куче не k, а только 1 элемент, на втором шаге — 2 элемента, потом 3, 4 ... k?

Нет, я совсем не это имею ввиду.
Наверное, я слишком плохо объясняю.

Здравствуйте, PaulMinelly, Вы писали:

PM>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
PM>Какие еще могут быть идеи за O(n) и память O(1).

Такая задача и ее решение описаны здесь (english):
http://www.ddj.com/architect/184405363

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, PaulMinelly, Вы писали:

PM>>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
PM>>Какие еще могут быть идеи за O(n) и память O(1).

А>Такая задача и ее решение описаны здесь (english):
А>http://www.ddj.com/architect/184405363

Небольшое замечание: у нас задача немного отличается, нам нужно k уникальных чисел.

_DA>Нет, я совсем не это имею ввиду.
_DA>Наверное, я слишком плохо объясняю.

Все клево! Сегодня прочитал Кормена — понял что куча действительно строится за O(n), а O(nlogn) — было у Бентли это не самая точная оценка сверху. Спасибо тебе!

Теперь я понял твой вариант с хешем, но он потребует памяти O(n).

Теперь я понимаю что можно построить кучу из первых K больших элементов, а потом ее отсортировать и выкинуть дубликаты Получится O(N + klogk). Память O(1). Тоже как-то не круто. Блин, может эта задача не имеет более нормального решения?

Здравствуйте, PaulMinelly, Вы писали:

PM>Теперь я понимаю что можно построить кучу из первых K больших элементов, а потом ее отсортировать и выкинуть дубликаты :) Получится O(N + klogk). Память O(1).

Только вот я теперь не понимаю, как ты добьешься такой сложности :) Если изначально не выбросить повторы, то я не вижу, как с помощью кучи сделать что-то лучше O(nlogn).

PM>Тоже как-то не круто. Блин, может эта задача не имеет более нормального решения? :)

PM>>Теперь я понимаю что можно построить кучу из первых K больших элементов, а потом ее отсортировать и выкинуть дубликаты Получится O(N + klogk). Память O(1).

_DA>Только вот я теперь не понимаю, как ты добьешься такой сложности Если изначально не выбросить повторы, то я не вижу, как с помощью кучи сделать что-то лучше O(nlogn).

Ну O(N + klogk) можно добиться, я не вижу сейчас сложностей, смотри:
O(N) — строим кучу прямо в имеющемся массиве inplace.
Выбираем k уникальных элементов из кучи. (т.е. их может быть больше k если они не уникальные, но не важно)= выбираем k уникальных = O(klogk) — это не точная верхняя оценка, но все равно подходит. И так сумма будет:
O(N) + O(klogk) = O(N + klogk)

Разве не правильно?

Здравствуйте, PaulMinelly, Вы писали:

PM>>>Теперь я понимаю что можно построить кучу из первых K больших элементов, а потом ее отсортировать и выкинуть дубликаты Получится O(N + klogk). Память O(1).

_DA>>Только вот я теперь не понимаю, как ты добьешься такой сложности Если изначально не выбросить повторы, то я не вижу, как с помощью кучи сделать что-то лучше O(nlogn).

PM>Ну O(N + klogk) можно добиться, я не вижу сейчас сложностей, смотри:
PM>O(N) — строим кучу прямо в имеющемся массиве inplace.

PM>Выбираем k уникальных элементов из кучи. (т.е. их может быть больше k если они не уникальные, но не важно)= выбираем k уникальных = O(klogk) — это не точная верхняя оценка, но все равно подходит. И так сумма будет:

У тебя тут две ошибки. Во-первых, у нас в куче N элементов, поэтому логарифм должен быть от N, ну а во-вторых, чтобы выбрать k уникальных из кучи, возможно понадобится выбрать полностью все элементы. Например, у тебя в куче будет лежать 100 единичек, 100 двоек и одна тройка, тройку ты достанешь на 201 шаге. Так что оценка этого алгоритма — O(nlogn).

PM>O(N) + O(klogk) = O(N + klogk)

PM>Разве не правильно?

Здравствуйте, PaulMinelly, Вы писали:

PM>Дан массив [1;n]
PM>- содержащий n целых числел (32 битных integer);
PM>- массив НЕ отсортирован;
PM>- в массиве есть дубликаты;

PM>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
PM>Т.е. в массиве {1,2,3,3,4} при k=3 ответ будет 2,3,4 а не 3,3,4.

Берете очередь размером не больше, чем k (т.е., если при добавлении очередного элемента в начало очереди ее размер становится больше k, элемент из конца очереди удаляется).

Засовываете в очередь первый элемент массива. Затем бежите по массиву, и если очередной элемент больше, чем элемент в начале очереди, добавляете его в очередь.

Обратите внимание, что 1) очередь отсортирована по убыванию (первый элемент всегда самый большой) 2) в ней нет повторяющихся элементов — это инвариант вашего цикла.

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

Сложность алгоритма, очевидно, O(n), требование к памяти — O(k).

Здравствуйте, Pzz, Вы писали:

Pzz>Берете очередь размером не больше, чем k (т.е., если при добавлении очередного элемента в начало очереди ее размер становится больше k, элемент из конца очереди удаляется).

Pzz>Засовываете в очередь первый элемент массива. Затем бежите по массиву, и если очередной элемент больше, чем элемент в начале очереди, добавляете его в очередь.

Pzz>Обратите внимание, что 1) очередь отсортирована по убыванию (первый элемент всегда самый большой) 2) в ней нет повторяющихся элементов — это инвариант вашего цикла.

Pzz>На выходе из цикла в очереди содержится k максимальных и уникальных чисел. Доказательство этого факта и того, что цикл сохраняет свой инвариант оставляю пытливому читателю

Pzz>Сложность алгоритма, очевидно, O(n), требование к памяти — O(k).

"For every complex problem, there is a solution that is simple, neat, and wrong."

Предлагаю пару тестов:

5 4 3 2 1, k = 3
5 6 4 7 3 8 2 9 1 10, k = 8
1 1 3 3 5 5 7 7 6 6 4 4 2 2, k = 5

Здравствуйте, _DAle_, Вы писали:

_DA>"For every complex problem, there is a solution that is simple, neat, and wrong."

Хм.

PM>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
PM>Какие еще могут быть идеи за O(n) и память O(1).

Аффтар, а решение вообще существует? И можно ли таковым считать поразрядную сортировку (у которой число итераций не менее O(log(n)))?

В принципе я знаю решение, но или без дубликатов, или для неуникальных чисел. Зато оно годится для любых сравниваемых данных (не обязательно чисел).

Pzz>Обратите внимание, что 1) очередь отсортирована по убыванию (первый элемент всегда самый большой) 2) в ней нет повторяющихся элементов — это инвариант вашего цикла.
_DA>>"For every complex problem, there is a solution that is simple, neat, and wrong."

Pzz>Хм.

Сложность у вас O(nk), а может даже O(nkk). k на поиск дубликата последовательным перебором, и если нет дубликата то сдвиг всех элементов и вставка нового элемента = это второе k. Так что k^2. Можно сделать циклическую очередь тогда kk не будет, будет k и финал тогда O(nk) все равно, хотя надо поразмыслить тщательнее.

PM>>Ну O(N + klogk) можно добиться, я не вижу сейчас сложностей, смотри:
PM>>O(N) — строим кучу прямо в имеющемся массиве inplace.

PM>>Выбираем k уникальных элементов из кучи. (т.е. их может быть больше k если они не уникальные, но не важно)= выбираем k уникальных = O(klogk) — это не точная верхняя оценка, но все равно подходит. И так сумма будет:

_DA>У тебя тут две ошибки. Во-первых, у нас в куче N элементов, поэтому логарифм должен быть от N, ну а во-вторых, чтобы выбрать k уникальных из кучи, возможно понадобится выбрать полностью все элементы. Например, у тебя в куче будет лежать 100 единичек, 100 двоек и одна тройка, тройку ты достанешь на 201 шаге. Так что оценка этого алгоритма — O(nlogn).

С этим придется согласиться.

PM>>Надо найти k-первых максимальных (и уникальных) чисел в массиве (k<N).
PM>>Какие еще могут быть идеи за O(n) и память O(1).

S>Аффтар, а решение вообще существует? И можно ли таковым считать поразрядную сортировку (у которой число итераций не менее O(log(n)))?
S>В принципе я знаю решение, но или без дубликатов, или для неуникальных чисел. Зато оно годится для любых сравниваемых данных (не обязательно чисел).

Если бы я знал Решений уже много предложили. Я срашиваю потому что не знаю. Хочу образоваться
Если бы в массиве n элементов не содержалось дубликатов — тогда применяем order statistics за O(n). Все просто.

PM>Если бы я знал Решений уже много предложили.
Вообще идея убрать дубликаты за О(n) времени и О(1) памяти выглядит достаточно глухо. Ну разве что радикс.

PM>Если бы в массиве n элементов не содержалось дубликатов — тогда применяем order statistics за O(n). Все просто.
А что такое order statistics? Я знаю решение, использующее метод упорядочивания элементов относительно медианы как в быстрой сортировке, но только применяющаяся к одному из двух подмассивов. Если выбирать медиану случайным образом, будет практически всегда работать за О(n).

Здравствуйте, subdmitry, Вы писали:

PM>>Если бы я знал Решений уже много предложили.
S>Вообще идея убрать дубликаты за О(n) времени и О(1) памяти выглядит достаточно глухо. Ну разве что радикс.

PM>>Если бы в массиве n элементов не содержалось дубликатов — тогда применяем order statistics за O(n). Все просто.
S>А что такое order statistics? Я знаю решение, использующее метод упорядочивания элементов относительно медианы как в быстрой сортировке, но только применяющаяся к одному из двух подмассивов. Если выбирать медиану случайным образом, будет практически всегда работать за О(n).

По-видимому, речь идет о нем.

Partition-based_general_selection_algorithm

Здравствуйте, PaulMinelly, Вы писали:

PM>Сложность у вас O(nk), а может даже O(nkk). k на поиск дубликата последовательным перебором, и если нет дубликата то сдвиг всех элементов и вставка нового элемента = это второе k. Так что k^2. Можно сделать циклическую очередь тогда kk не будет, будет k и финал тогда O(nk) все равно, хотя надо поразмыслить тщательнее.

Только O( Nk ) всё-таки.
Ты за O( k ) ищешь место для вставки и ещё за O( k ) сдвигаешь хвост массива. Но O( k ) + O( k ) =def= O( k )