Обобщение стека find-min/find-max на статистику произвольного порядка?

Ответ 1

Так как структуру можно использовать для сортировки k элементов с операциями push и find-k O (k), каждая реализация на основе сравнения имеет по крайней мере одну из этих затрат Omega (log k), даже в амортизированном смысле, с рандомизации.

Push может быть O (log k), а pop/find-kth может быть O (1) (использовать постоянные структуры данных, push должен предварительно скорректировать статистику заказа). Мое чувство кишки, основанное на работе с нижними границами для алгоритмов на основе сравнения, состоит в том, что O (1) push/pop и O (log k) find-kth выполнимы, но требуют амортизации.

Ответ 2

Является ли это на самом деле быстрее, чем реализация log k, в зависимости от того, какие операции используются наиболее часто, я предлагаю реализацию с O (1) Find-kth и Pop и O (n) Push, где n - размер стека, И я также хочу поделиться этим с SO, потому что это просто веселая структура данных с первого взгляда, но может даже быть разумной.

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

Как обычный связанный стек, самой коллекции нужно будет поддерживать ссылку на верхний node (и на дно?). Чтобы разместить O (1) природу метода Find-k, коллекция также сохранит ссылку на k-й наибольший элемент.

Поп-метод работает следующим образом: Выбранный node удаляется из отсортированного дважды связанного списка, как удаление из обычного отсортированного связанного списка. Он принимает O (1), поскольку коллекция имеет ссылку на верхнюю. В зависимости от того, был ли popped элемент больше или меньше, чем k-ый элемент, ссылка на k-й наибольший элемент устанавливается либо в предыдущий, либо следующий. Таким образом, метод все еще имеет сложность O (1).

Метод push работает так же, как и нормальное дополнение к отсортированному связанному списку, который является операцией O (n). Он начинается с самого маленького элемента и вставляет новый node, когда встречается более крупный элемент. Чтобы поддерживать правильную ссылку на k-й наибольший элемент, выбирается либо предыдущий, либо следующий элемент для текущего k-го наибольшего элемента, в зависимости от того, был ли нажатый node больше или меньше, чем k-ый наибольший элемент.

Конечно, рядом с этим ссылка на верхнюю часть стека должна быть установлена ​​в обоих методах. Также существует проблема k > n, для которой вы не указали, что должна делать структура данных. Я надеюсь, что это ясно, как это работает, иначе я мог бы добавить пример.

Но хорошо, не совсем то, на что вы надеялись, но я нахожу это интересным "решением".

Изменить: реализация описанной структуры

В этом вопросе была выпущена щедрость, которая указывает, что мой первоначальный ответ не был достаточно хорошим: P Возможно, OP хотел бы увидеть реализацию?

В С# я реализовал как медианную проблему, так и проблему с фиксированным k. Реализация трекера медианы - это всего лишь обертка вокруг трекера k-го элемента, где k может мутировать.

Чтобы повторить сложности:

• Push принимает O (n)
• Поп принимает O (1)
• FindKth принимает O (1)
• Изменение k принимает O (delta k)

Я уже подробно описал алгоритм в своем оригинальном посте. Внедрение тогда довольно просто (но не настолько тривиально, чтобы получить право, так как есть много признаков неравенства и если утверждения считать). Я прокомментировал только, чтобы указать, что сделано, но не детали того, как, иначе это стало бы слишком большим. Код уже достаточно длинный для сообщения SO.

Я хочу предоставить контракты всех нетривиальных публичных членов:

• K - это индекс элемента в отсортированном связанном списке, чтобы сохранить ссылку. Является ли он изменчивым, и когда он установлен, структура немедленно исправляется для этого.
• KthValue - это значение в этом индексе, если структура еще не имеет элементов k, и в этом случае она возвращает значение по умолчанию.
• HasKthValue существует, чтобы легко отличить эти значения по умолчанию от элементов, которые оказались значением по умолчанию для его типа.
• Constructors: нуль перечисляемый интерпретируется как пустой перечислимый, а нулевой сравнитель интерпретируется как значение по умолчанию. Этот компаратор определяет порядок, используемый при определении k-го значения.

Итак, это код:

public sealed class KthTrackingStack<T>
{
    private readonly Stack<Node> stack;
    private readonly IComparer<T> comparer;
    private int k;
    private Node smallestNode;
    private Node kthNode;

    public int K
    {
        get { return this.k; }
        set
        {
            if (value < 0) throw new ArgumentOutOfRangeException();
            for (; k < value; k++)
            {
                if (kthNode.NextInOrder == null)
                    return;
                kthNode = kthNode.NextInOrder;
            }
            for (; k >= value; k--)
            {
                if (kthNode.PreviousInOrder == null)
                    return;
                kthNode = kthNode.PreviousInOrder;
            }
        }
    }
    public T KthValue
    {
        get { return HasKthValue ? kthNode.Value : default(T); }
    }
    public bool HasKthValue
    {
        get { return k < Count; }
    }
    public int Count
    {
        get { return this.stack.Count; }
    }

    public KthTrackingStack(int k, IEnumerable<T> initialElements = null, IComparer<T> comparer = null)
    {
        if (k < 0) throw new ArgumentOutOfRangeException("k");
        this.k = k;
        this.comparer = comparer ?? Comparer<T>.Default;
        this.stack = new Stack<Node>();
        if (initialElements != null)
            foreach (T initialElement in initialElements)
                this.Push(initialElement);
    }
    public void Push(T value)
    {
        //just a like a normal sorted linked list should the node before the inserted node be found.
        Node nodeBeforeNewNode;
        if (smallestNode == null || comparer.Compare(value, smallestNode.Value) < 0)
            nodeBeforeNewNode = null;
        else
        {
            nodeBeforeNewNode = smallestNode;//untested optimization: nodeBeforeNewNode = comparer.Compare(value, kthNode.Value) < 0 ? smallestNode : kthNode;
            while (nodeBeforeNewNode.NextInOrder != null && comparerCompare(value, nodeBeforeNewNode.NextInOrder.Value) > 0)
                nodeBeforeNewNode = nodeBeforeNewNode.NextInOrder;
        }
        //the following code includes the new node in the ordered linked list
        Node newNode = new Node
                        {
                            Value = value,
                            PreviousInOrder = nodeBeforeNewNode,
                            NextInOrder = nodeBeforeNewNode == null ? smallestNode : nodeBeforeNewNode.NextInOrder
                        };
        if (newNode.NextInOrder != null)
            newNode.NextInOrder.PreviousInOrder = newNode;
        if (newNode.PreviousInOrder != null)
            newNode.PreviousInOrder.NextInOrder = newNode;
        else
            smallestNode = newNode;
        //the following code deals with changes to the kth node due the adding the new node
        if (kthNode != null && comparer.Compare(value, kthNode.Value) < 0)
        {
            if (HasKthValue)
                kthNode = kthNode.PreviousInOrder;
        }
        else if (!HasKthValue)
        {
            kthNode = newNode;
        }
        stack.Push(newNode);
    }

    public T Pop()
    {
        Node result = stack.Pop();
        //the following code deals with changes to the kth node
        if (HasKthValue)
        {
            if (comparer.Compare(result.Value, kthNode.Value) <= 0)
                kthNode = kthNode.NextInOrder;
        }
    else if(kthNode.PreviousInOrder != null || Count == 0)
        {
            kthNode = kthNode.PreviousInOrder;
        }
        //the following code maintains the order in the linked list
        if (result.NextInOrder != null)
            result.NextInOrder.PreviousInOrder = result.PreviousInOrder;
        if (result.PreviousInOrder != null)
            result.PreviousInOrder.NextInOrder = result.NextInOrder;
        else
            smallestNode = result.NextInOrder;
        return result.Value;
    }
    public T Peek()
    {
        return this.stack.Peek().Value;
    }
    private sealed class Node
    {
        public T Value { get; set; }
        public Node NextInOrder { get; internal set; }
        public Node PreviousInOrder { get; internal set; }
    }
}
public class MedianTrackingStack<T>
{
    private readonly KthTrackingStack<T> stack;
    public void Push(T value)
    {
        stack.Push(value);
        stack.K = stack.Count / 2;
    }
    public T Pop()
    {
        T result = stack.Pop();
        stack.K = stack.Count / 2;
        return result;
    }

    public T Median
    {
        get { return stack.KthValue; }
    }
    public MedianTrackingStack(IEnumerable<T> initialElements = null, IComparer<T> comparer = null)
    {
        stack = new KthTrackingStack<T>(initialElements == null ? 0 : initialElements.Count()/2, initialElements, comparer);
    }
}

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

Ответ 3

Я думаю, что то, что говорил тоф, реализует чисто функциональную структуру данных, которая поддерживает только O (log k) insert и O (1) find-kth (кэшируется вставкой), а затем создает стек этих структур. Вставляйте вставки в верхнюю версию и выталкиваете обновление, поп выводит верхнюю версию, а find-kth работает в верхней версии. Это O (log k)/O (1)/(1), но суперлинейное пространство.

EDIT: Я работал над O (1) push/O (1) pop/O (log k) find-kth, и я думаю, что это невозможно. Алгоритм сортировки, упомянутый tophat, может быть адаптирован для получения равномерно распределенной статистики порядка массива length-k за время O (k + (√k) log k). Проблема заключается в том, что алгоритм должен знать, как каждая статистика порядка сравнивается со всеми другими элементами (иначе это может быть неправильно), а это означает, что оно перевело все на один из кодов √k + 1, который принимает Ω (k log (√k + 1)) = Ω (k log k) сравнений по теоретико-информационным основаниям. К сожалению.

Заменяя √k на k ^eps для любого ep > 0, с O (1) push/O (1) pop, я не думаю, что find-kth может быть O (k ^{1 - eps}), даже с рандомизацией и амортизацией.

Ответ 4

Вы можете использовать список пропуска. (Я сначала подумал о связанном списке, но вставка O (n) и amit скорректировала меня с помощью списка пропуска. Я думаю, что эта структура данных может быть довольно интересной в вашем случае)

With this data structure, inserting/deleting would take O(ln(k))

and finding the maximum O(1)

Я бы использовал:

• стек, содержащий ваши элементы
• a стек, содержащий историю списка пропусков (содержащую k наименьших элементов)

(я понял, что это был Kth самый большой... элемент, но это почти та же проблема)

при нажатии (O (ln (k)):

если элемент меньше k-го элемента, удалите k-й элемент (O (ln (k)) поместите его в кучу LIFO (O (1)), затем вставьте элемент в список пропусков O (ln (k) )

в противном случае он не в списке пропуска просто положил его на кучу (O (1))

При нажатии вы добавляете новый список пропусков в историю, так как это похоже на копию при записи, это не займет больше O (ln (k))

при нажатии (O (1):

вы просто выходите из обоих стеков

Получение k-го элемента O (1):

всегда принимать максимальный элемент в списке (O (1))

Все ln (k) являются амортизированной стоимостью.

Пример:

Я возьму тот же пример, что и ваш (в Stack с find-min/find-max более эффективным, чем O (n)):

Предположим, что у нас есть стек и добавьте значения 2, 7, 1, 8, 3 и 9 в этом порядке. и k = 3

Я буду представлять его следующим образом:

[number in the stack] [ skip list  linked with that number]

сначала я нажимаю 2,7 и 1 (это не делает смысл искать k-й элемент в списке из менее чем элементов k)

1 [7,2,1] 
7 [7,2,null]
2 [2,null,null]

Если мне нужен элемент kth, мне просто нужно взять max в связанном списке: 7

теперь я нажимаю 8,3, 9

в верхней части стека у меня:

8 [7,2,1] since 8 > kth element  therefore skip list doesn't change

тогда:

3 [3,2,1] since 3 < kth element, the kth element has changed. I first delete 7 who was the previous kth element (O(ln(k))) then insert 3 O(ln(k)) => total O(ln(k))

тогда:

9 [3,2,1] since 9 > kth element

Вот стек, который я получаю:

9 [3,2,1]
3 [3,2,1]
8 [7,2,1]
1 [7,2,1] 
7 [7,2,null]
2 [2,null,null]

найти k-й элемент:

I get 3 in O(1)

теперь я могу поп 9 и 3 (принимает O (1)):

8 [7,2,1]
1 [7,2,1] 
7 [7,2,null]
2 [2,null,null]

найти k-й элемент:

I get 7 in O(1)

и нажмите 0 (принимает O (ln (k) - вставка)

0 [2,1,0]
8 [7,2,1]
1 [7,2,1] 
7 [7,2,null]
2 [2,null,null]

Ответ 5

Единственная реальная рабочая реализация, которую я могу обернуть вокруг, - Push/Pop O (log k) и Kth O (1).

• Стек (с одной связью)
• Min Heap (размер k)
• Stack2 (дважды связан)
• Узлы значений будут совместно использоваться между Stack, Heap и Stack2

PUSH:

• Нажмите в стек
• Если значение >= heap root
• • Если размер кучи < к
• • • Вставить значение в кучу
• • Else
• • • Удалить корень кучи
• • • Удалите кучу кучи в стек2.
• • • Вставить значение в кучу

POP:

• Поп из стека
• Если popped node имеет ссылки на stack2
• • Удалить из stack2 (удалить дважды связанный список)
• Если popped node имеет ссылки на кучи
• • Удалить из кучи (свопинг с последним элементом, выполнить кучу вверх-вниз)
• • Поп из stack2
• • Если элемент, вставленный из stack2, не равен null
• • • Элемент Insert, вставленный из stack2 в кучу

КТН:

• Если куча имеет размер k
• • Возвращает значение корня кучи

Ответ 6

Что делать, если вы связали стек с парой Fibonacci Heaps? Это может привести к амортизации O (1) Push и FindKth, а O (lgN) удалить.

В стеке хранятся пары [value, heapPointer]. Указатели стека хранилищ кучи.
Создайте один MaxHeap, один MinHeap.

В Push:
если MaxHeap имеет менее K элементов, вставьте верхнюю часть стека в MaxHeap,
else, если новое значение меньше вершины MaxHeap, сначала вставьте результат DeleteMax в MinHeap, затем вставьте новый элемент в MaxHeap;
иначе вставьте его в MinHeap. O (1) (или O (lgK), если требуется DeleteMax)

В FindKth верните верх MaxHeap. O (1)

В Pop, также сделайте Delete (node) из кучи всплывающих элементов.
Если это было в MinHeap, все готово. O (ЛГН)
Если это было в MaxHeap, также выполните DeleteMin из MinHeap и вставьте результат в MaxHeap. О (ЛГК) + O (ЛГН) + O (1)

Обновление:
Я понял, что написал это как К'т, самый маленький, но не самый большой. Я также забыл шаг, когда новое значение меньше текущего K'th наименьшего. И этот шаг толкает наихудший случай обратно на O (lg K). Это может быть все равно для равномерно распределенного ввода и малого K, так как он попадет в этот случай только для вставок K/N.

* _{перенесла новую идею на другой ответ - она ​​стала слишком большой.}

Ответ 7

@tophat прав - поскольку эту структуру можно использовать для реализации сортировки, она не может иметь меньшую сложность, чем эквивалентный алгоритм сортировки. Итак, как вы делаете что-то меньшее, чем O (lg N)? Используйте Radix Sort.

Вот реализация, в которой используется Binary Trie. Вставка элементов в двоичное Trie - это, по сути, такая же операция, как и сортировка radix. Стоимость вставки и удаления s O (m), где m - константа: количество бит в ключе. Поиск следующего по величине или наименьшему ключу также O (m), выполненный путем следующего шага в первом прохождении по глубине в порядке.

Итак, общая идея состоит в том, чтобы использовать значения, вставляемые в стек как ключи в trie. Данные для хранения - это счетчик событий этого элемента в стеке. Для каждого нажатого элемента: если он существует в trie, увеличьте его количество, иначе сохраните его с количеством 1. Когда вы поместите элемент, найдите его, уменьшите счет и удалите его, если счет теперь равен 0. Оба этих операциями являются O (m).

Чтобы получить O (1) FindKth, отслеживайте 2 значения: значение элемента Kth и количество экземпляров этого значения в первом элементе K. (например, для K = 4 и стека [1,2,3,2,0,2], значение Kth равно 2, а "iCount" равно 2.) Затем, когда вы нажимаете значения < KthValue, вы просто уменьшаете счетчик экземпляров, а если он равен 0, найдите FindPrev в trie, чтобы получить следующее меньшее значение.

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

(Правила отличаются друг от друга, если элементов меньше K. В этом случае вы можете просто отслеживать максимальное вставленное значение. Когда есть элементы K, max будет Kth.)

Вот реализация C. Он опирается на BinaryTrie (построенный с использованием примера в PineWiki в качестве базы) с этим интерфейсом:

BTrie* BTrieInsert(BTrie* t, Item key, int data);
BTrie* BTrieFind(BTrie* t, Item key);
BTrie* BTrieDelete(BTrie* t, Item key);
BTrie* BTrieNextKey(BTrie* t, Item key);
BTrie* BTriePrevKey(BTrie* t, Item key);

Вот функция Push.

void KSStackPush(KStack* ks, Item val)
{
   BTrie* node;
   //resize if needed
   if (ks->ct == ks->sz) ks->stack = realloc(ks->stack,sizeof(Item)*(ks->sz*=2)); 

   //push val
   ks->stack[ks->ct++]=val;

   //record count of value instances in trie
   node = BTrieFind(ks->trie, val);
   if (node) node->data++;
   else ks->trie = BTrieInsert(ks->trie, val, 1);

   //adjust kth if needed
   ksCheckDecreaseKth(ks,val);
}

Вот помощник для отслеживания KthValue

//check if inserted val is in set of K
void ksCheckDecreaseKth(KStack* ks, Item val)
{
   //if less than K items, track the max.
   if (ks->ct <= ks->K) {
      if (ks->ct==1) { ks->kthValue = val; ks->iCount = 1;} //1st item
      else if (val == ks->kthValue) { ks->iCount++; }
      else if (val > ks->kthValue) { ks->kthValue = val; ks->iCount = 1;}
   }

   //else if value is one of the K, decrement instance count
   else if (val < ks->kthValue &&  (--ks->iCount<=0))  {
      //if that was only instance in set,
      //find the previous value, include all its instances
      BTrie* node = BTriePrev(ks->trie, ks->kthValue);
      ks->kthValue = node->key;
      ks->iCount = node->data;
   }
}

Вот функция Pop

Item KSStackPop(KStack* ks)
{
   //pop val
   Item val = ks->stack[--ks->ct];
   //find in trie
   BTrie* node = BTrieFind(ks->trie, val);
   //decrement count, remove if no more instances
   if (--node->data == 0)
      ks->trie = BTrieDelete(ks->trie, val);
   //adjust kth if needed
   ksCheckIncreaseKth(ks,val);
   return val;
}

И помощник для увеличения KthValue

//check if removing val causes Kth to increase
void ksCheckIncreaseKth(KStack* ks, Item val)
{
   //if less than K items, track max
   if (ks->ct < ks->K)
   {  //if removing the max,
      if (val==ks->kthValue) {
         //find the previous node, and set the instance count.
         BTrie* node = BTriePrev(ks->trie, ks->kthValue);
         ks->kthValue = node->key;
         ks->iCount = node->data;
      }
   }
   //if removed val was among the set of K,add a new item
   else if (val <= ks->kthValue)
   {
      BTrie* node = BTrieFind(ks->trie, ks->kthValue);
      //if more instances of kthValue exist, add 1 to set. 
      if (node && ks->iCount < node->data) ks->iCount++;
      //else include 1 instance of next value
      else {
         BTrie* node = BTrieNext(ks->trie, ks->kthValue);
         ks->kthValue = node->key;
         ks->iCount = 1;
      }
   }
}

Итак, это алгоритм O (1) для всех трех операций. Он также может поддерживать операцию Median: Начать с KthValue = первое значение, и когда размер стека изменяется на 2, выполните операцию IncreaseKth или DecreasesKth. Недостатком является то, что константа велика. Это только выигрыш, когда m < ЛГК. Однако для маленьких клавиш и большого K это может быть хорошим выбором.

Ответ 8

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

При вставке (нажатии) для каждого пути хранится счетчик, в котором хранится количество вставленных там элементов. Это позволит каждому node отслеживать, сколько элементов было вставлено с использованием этого пути, т.е. Число представляет количество элементов, которые хранятся ниже этого пути. Таким образом, когда вы пытаетесь найти k-й элемент, это будет простое сравнение на каждом пути.

Для popping вы можете иметь статический объект, который имеет ссылку на последний сохраненный объект. Этот объект можно получить из корневого объекта, следовательно, O (1). Конечно, вам нужно будет добавить функции для извлечения последнего вставленного объекта, что означает, что вновь нажатый node должен иметь указатель на ранее вставляемый элемент (реализованный в процедуре push, очень простой, также O (1)). Вам также необходимо уменьшить счетчик, что означает, что каждый node должен иметь указатель на родительский node (также простой).

Для нахождения k-го элемента (это для наименьшего k-го элемента, но поиск самого большого очень похож): когда вы вводите каждый node, вы передаете k и минимальный индекс для ветки (для корня это будет 0). Затем вы делаете простой, если сравнивать для каждого пути: if (k между минимальным индексом и минимальным индексом + pathCounter), вы вводите этот путь, проходящий в k, и новый минимальный индекс как (минимальный индекс + сумма всех предыдущих pathCounters, за исключением одного ты взял). Я думаю, что это O (1), так как увеличение числа данных в определенном диапазоне не увеличивает трудность нахождения k.

Я надеюсь, что это поможет, и если что-то не очень ясно, просто дайте мне знать.