![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
migmitНаткнулся тут на простенькую задачку: написать стек, поддерживающий, кроме стандартных push и pop, ещё и операцию min, которая возвращает минимальное значение из содержащихся в стеке. При этом все три операции должны выполняться за O(1).
Ну, задачка действительно простая, но меня натолкнула на мысль: а что, если вместо стека делать deque, т.е., массив элементов, к которому можно добавлять новые (и удалять старые) как с левого конца, так и с правого? При этом по-прежнему хочется делать min.
Пока что у меня получилась реализация, делающая pop_front, pop_back и min за O(1), а push_back и push_front - за амортизированное O(1).
Вопрос к коллегам: это где-нибудь есть?
Ну, задачка действительно простая, но меня натолкнула на мысль: а что, если вместо стека делать deque, т.е., массив элементов, к которому можно добавлять новые (и удалять старые) как с левого конца, так и с правого? При этом по-прежнему хочется делать min.
Пока что у меня получилась реализация, делающая pop_front, pop_back и min за O(1), а push_back и push_front - за амортизированное O(1).
Вопрос к коллегам: это где-нибудь есть?
no subject
Date: 2014-03-24 03:58 pm (UTC)no subject
Date: 2014-03-24 04:03 pm (UTC)no subject
Date: 2014-03-24 06:38 pm (UTC)no subject
Date: 2014-03-25 02:08 pm (UTC)а) делать get_min, являющийся частным случаем pop_min
б) выполнять другие операции (pop_front и pop_back)
Очевидно, что любая priority queue умеет пункт А. Соответственно, я посоветовал полистать литературу на тему priority queue, может окажется, что некоторые варианты умеют нужные Вам операции, ну и заполучить нужные ключевые слова.
А какая это реализация priority queue выделена Вами как классическая? array-backed binary heap?
no subject
Date: 2014-03-25 06:04 pm (UTC)Кроме того, подразумеваемым обычно свойством priority queue является частичное НЕсохранение порядка, в то время как нам нужно держать порядок точно.
Короче говоря, страшно далеки они от того, что надо. Впрочем, решение с амортизированным O(1) я, как уже говорил, придумал, а ниже привели решение с настоящим O(1). И ни то, ни другое не имеет отношения к priority queue.
> array-backed binary heap?
Она, родимая.
no subject
Date: 2014-03-24 04:21 pm (UTC)no subject
Date: 2014-03-24 06:39 pm (UTC)no subject
Date: 2014-03-24 05:43 pm (UTC)Если достаточно амортизированного O(1), то выкидываем идею про recursive slow-down (вместе с расскраской и счетчиками) -- и получаем, фактически, rope (http://en.wikipedia.org/wiki/Rope_(data_structure)) на основе леса полных деревьев.
no subject
Date: 2014-03-24 06:39 pm (UTC)no subject
Date: 2014-03-24 07:15 pm (UTC)no subject
Date: 2014-03-24 07:39 pm (UTC)no subject
Date: 2014-03-24 07:59 pm (UTC)no subject
Date: 2014-03-25 07:07 am (UTC)no subject
Date: 2014-03-25 07:18 am (UTC)no subject
Date: 2014-03-25 07:25 am (UTC)no subject
Date: 2014-03-25 07:26 am (UTC)no subject
Date: 2014-03-25 08:06 am (UTC)Запись в ячейку min производится только если новое значение меньше старого min
no subject
Date: 2014-03-25 09:31 am (UTC)no subject
Date: 2014-03-25 09:45 am (UTC)проверка стоит недорого, а изменятся значение min будет редко
no subject
Date: 2014-03-25 10:05 am (UTC)no subject
Date: 2014-03-25 10:17 am (UTC)no subject
Date: 2014-03-25 10:42 am (UTC)По-нормальному нужно просто держать два стека, один обычный, а другой состоящий из тех элементов первого, глубже которых нет ни одного элемента меньше. Будет O(1) на push, pop и min.
no subject
Date: 2014-03-25 10:56 am (UTC)no subject
Date: 2014-03-25 11:21 am (UTC)no subject
Date: 2014-03-25 11:58 am (UTC)no subject
Date: 2014-03-25 12:04 pm (UTC)no subject
Date: 2014-03-25 12:27 pm (UTC)no subject
Date: 2014-03-25 06:05 pm (UTC)Я не сомневаюсь, что в курсе, но людей, на голубом глазу утверждавших, что O(2N) и O(N) — разные вещи, я видел.
no subject
Date: 2014-03-25 06:29 pm (UTC)Я решил, что это такая подколка. Ведь так в итоге и получается.
утверждавших, что O(2N) и O(N) — разные вещи
Уже интересно, что они говорили за O(N+1).