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

Question

В в этом предыдущем вопросе OP запросил структуру данных, аналогичную стеку, поддерживающему следующие операции в O (1) раз каждый:

• Push, который добавляет новый элемент поверх стека,
• Pop, который удаляет верхний элемент из стека,
• Find-Max, который возвращает (но не удаляет) наибольшееэлемент стека и
• Find-Min, который возвращает (но не удаляет) наименьший элемент стека.

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

• Push, который помещает элемент поверх стека,
• Pop, который выскакиваетвершина стека и
• Find-Kth, который для фиксированного k, определенного при создании структуры , возвращает k-й по величине элемент стека.

Можно поддерживать все эти операции, храня стек и сбалансированное двоичное дерево поиска, содержащее верхние k элементов, что позволило бы всем этим операциям выполняться за O (log k).У меня такой вопрос: возможно ли реализовать описанную выше структуру данных быстрее, чем эта? То есть, мы можем получить O (1) для всех трех операций?Или, возможно, O (1) для push и pop и O (log k) для поиска статистики заказов?

Answer 1

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

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

Answer 2

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

РЕДАКТИРОВАТЬ: я работал над O (1) push / O (1) pop / O (log k) найти-к-й, и я думаю, что это не может быть сделано.Алгоритм сортировки, на который ссылается tophat, может быть адаптирован для получения √k равномерно распределенной статистики порядка массива длины k за время O (k + (√k) log k).Проблема в том, что алгоритм должен знать, как статистика каждого заказа сравнивается со всеми остальными элементами (в противном случае это может быть неправильно), что означает, что он разбил все на части в одном из √k + 1 сегментов, что принимает Ω (k log (√k +1)) = Ω (k log k) сравнений по теоретико-информационным основаниям.Упс.

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

Answer 3

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

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

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

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

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

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

Но хорошо, не совсем сложность, на которую вы рассчитывали, но я считаю это интересным «решением».

---

Редактировать: Реализация описанной структуры

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

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

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

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

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

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

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

Так что это код:

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);
    }
}

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

Answer 4

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

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

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

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

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

(Правила различны, если элементов меньше, чем K. В этом случае вы можете просто отслеживать максимальное введенное значение. Когда K элементов, максимум будет 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) для всех 3 операций. Он также может поддерживать медианную операцию: начните с KthValue = первое значение, и всякий раз, когда размер стека изменяется на 2, выполняйте операцию IncreaseKth или DecreasesKth. Недостатком является то, что константа велика. Это только победа, когда m

Answer 5

Что если вы соединили стек с парой Куча Фибоначчи ? Это может дать амортизированные O (1) Push и FindKth, а O (lgN) удалить.

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

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

В FindKth верните вершину MaxHeap. O (1) * ** тысяча двадцать-один ** 1023 тысяча двадцать два * В режиме «Pop» также выполните команду «Удалить» (узел) из кучи добавленного элемента.
Если это было в MinHeap, вы сделали. O (ЛГН)
Если это было в MaxHeap, также выполните DeleteMin из MinHeap и вставьте результат в MaxHeap. * 1 031 ** * O тысячи тридцать две (ЛКИ) + O (ЛГНО) + O (1) * +1033 ** +1034 ** 1 035 * Обновление:
Я понял, что записал это как K'ths самый маленький, а не K'th самый большой. Я также забыл шаг, когда новое значение меньше текущего наименьшего. И этот шаг толкает наихудший случай вставки обратно к O (LG K). Это все еще может быть в порядке для равномерно распределенного ввода и малого K, так как это будет иметь место только в случае вставки K / N. * _{переместил New Idea в другой ответ - он стал слишком большим.}

Answer 6

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

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

PUSH:

• Толкнуть в стек
• Если значение> = корень кучи
• • Если размер кучи
• • • Вставить значение в кучу
• • прочее
• • • Удалить кучу корня
• • • Переместить удаленный корень кучи в стек2
• • • Вставить значение в кучу

POP:

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

КТН:

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

Answer 7

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

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

and finding the maximum O(1)

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

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

(я понял, что это былоK-й по величине ... элемент. но это в значительной степени та же проблема)

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

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

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

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

при щелчке (O (1):

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

получаякт элЭлемент O (1):

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

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

---

Пример:

Я возьму тот же пример, что и ваш (в стеке с 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]

Если я хочу k-й элемент, мне просто нужно взять максимум в связанном списке: 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]

найти kthэлемент:

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]

Answer 8

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

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

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

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

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