Generalizing the find-min/find-max stack to arbitrary order statistics?

Question

In this earlier question, the OP asked for a data structure similar to a stack supporting the following operations in O(1) time each:

• Push, which adds a new element atop the stack,
• Pop, which removes the top element from the stack,
• Find-Max, which returns (but does not remove) the largest element of the stack, and
• Find-Min, which returns (but does not remove) the smallest element of the stack.

A few minutes ago I found this related question asking for a clarification on a similar data structure that instead of allowing for the max and min to be queried, allows for the median element of the stack to be queried. These two data structures seem to be a special case of a more general data structure supporting the following operations:

• Push, which pushes an element atop the stack,
• Pop, which pops the top of the stack, and
• Find-Kth, which for a fixed k determined when the structure is created, returns the kth largest element of the stack.

It is possible to support all of these operations by storing a stack and an balanced binary search tree holding the top k elements, which would enable all these operations to run in O(log k) time. My question is this: is it possible to implement the above data structure faster than this? That is, could we get O(1) for all three operations? Or perhaps O(1) for push and pop and O(log k) for the order statistic lookup?

Answer 1

Since the structure can be used to sort k elements with O(k) push and find-kth operations, every comparison-based implementation has at least one of these cost Omega(log k), even in an amortized sense, with randomization.

Push can be O(log k) and pop/find-kth can be O(1) (use persistent data structures; push should precompute the order statistic). My gut feeling based on working with lower bounds for comparison-based algorithms is that O(1) push/pop and O(log k) find-kth is doable but requires amortization.

Answer 2

Whether this is actually faster than your log k implementation, depending on which operations are used most frequently, I propose an implementation with O(1) Find-kth and Pop and O(n) Push, where n is the stack size. And I also want to share this with SO because it is just a hilarious data structure at first sight, but might even be reasonable.

It's best described by a doubly doubly linked stack, or perhaps more easily dscribed as a hybrid of a linked stack and a doubly linked sorted list. Basically each node maintains 4 references to other nodes, the next and previous in stack order and the next and previous in sorted order on the element size. These two linked lists can be implemented using the same nodes, but they work completely seperately, i.e. the sorted linked list doesn't have to know about the stack order and vice versa.

Like a normal linked stack, the collection itself will need to maintain a reference to the top node (and to the bottom?). To accomodate the O(1) nature of the Find-kth method, the collection will also keep a reference to the kth largest element.

The pop method works as follows: The popped node gets removed from the sorted doubly linked list, just like a removal from a normal sorted linked list. It takes O(1) as the collection has a reference to the top. Depending on whether the popped element was larger or smaller than the kth element, the reference to the kth largest element is set to either the previous or the next. So the method still has O(1) complexity.

The push method works just like a normal addition to a sorted linked list, which is a O(n) operation. It start with the smallest element, and inserts the new node when a larger element is encountered. To maintain the correct reference to the kth largest element, again either the previous or next element to the current kth largest element is selected, depending on whether the pushed node was larger or smaller than the kth largest element.

Of course next to this, the reference to the 'top' of the stack has to be set in both methods. Also there's the problem of k > n, for which you haven't specified what the data structure should do. I hope it is clear how it works, otherwise I could add an example.

But ok, not entirely the complexity you had hoped for, but I find this an interesting 'solution'.

---

Edit: An implementation of the described structure

A bounty was issued on this question, which indicates my original answer wasn’t good enough:P Perhaps the OP would like to see an implementation?

I have implemented both the median problem and the fixed-k problem, in C#. The implementation of the tracker of the median is just a wrapper around the tracker of the kth element, where k can mutate.

To recap the complexities:

• Push takes O(n)
• Pop takes O(1)
• FindKth takes O(1)
• Change k takes O(delta k)

I have already described the algorithm in reasonable detail in my original post. The implementation is then fairly straightforward(but not so trivial to get right, as there are a lot of inequality signs and if statements to consider). I have commented only to indicate what is done, but not the details of how, as it would otherwise become too large. The code is already quite lengthy for a SO post.

I do want to provide the contracts of all non-trivial public members:

• K is the index of the element in the sorted linked list to keep a reference too. Is it mutable and when set, the structure is immediately corrected for that.
• KthValue is the value at that index, unless the structure doesn’t have k elements yet, in which case it returns a default value.
• HasKthValue exists to easily distinguish these default values from elements which happened to be the default value of its type.
• Constructors: a null enumerable is interpreted as an empty enumerable, and a null comparer is interpreted as the default. This comparer defines the order used when determining the kth value.

So this is the code:

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

Of course you're always free to ask any question about this code, as I realize some things may not be obvious from the description and sporadic comments

Answer 3

I think what tophat was saying is, implement a purely functional data structure that supports only O(log k) insert and O(1) find-kth (cached by insert), and then make a stack of these structures. Push inserts into the top version and pushes the update, pop pops the top version, and find-kth operates on the top version. This is O(log k)/O(1)/(1) but super-linear space.

EDIT: I was working on O(1) push/O(1) pop/O(log k) find-kth, and I think it can't be done. The sorting algorithm that tophat referred to can be adapted to get √k evenly spaced order statistics of a length-k array in time O(k + (√k) log k). Problem is, the algorithm must know how each order statistic compares with all other elements (otherwise it might be wrong), which means that it has bucketed everything into one of √k + 1 buckets, which takes Ω(k log (√k + 1)) = Ω(k log k) comparisons on information theoretic grounds. Oops.

Replacing √k by k^eps for any eps > 0, with O(1) push/O(1) pop, I don't think find-kth can be O(k^{1 - eps}), even with randomization and amortization.

Answer 4

You could use a skip list . (I first thought of linked-list, but insertion is O(n) and amit corrected me with skip list. I think this data structure could be pretty interesting in your case)

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

and finding the maximum O(1)

I would use :

• a stack, containing your elements
• a a stack containing the history of skip list (containing the k smallest elements)

(I realised it was the Kth largest..element. but it's pretty much the same problem)

when pushing (O(ln(k)):

if the element is less the kth element, delete the kth element (O(ln(k)) put it in the LIFO pile (O(1)) then insert the element in the skip list O(ln(k))

otherwise it's not in the skip list just put it on the pile (O(1))

When pushing you add a new skip list to the history, since this is similar to a copy on write it wouldn't take more than O(ln(k))

when popping (O(1):

you just pop from both stacks

getting kth element O(1):

always take the maximum element in the list (O(1))

All the ln(k) are amortised cost.

---

Example:

I will take the same example as yours (on Stack with find-min/find-max more efficient than O(n)) :

Suppose that we have a stack and add the values 2, 7, 1, 8, 3, and 9, in that order. and k = 3

I will represent it this way :

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

first I push 2,7 and 1 (it doesn't make sens to look for the kth element in a list of less than k elements)

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

If I want the kth element I just need to take the max in the linked list: 7

now I push 8,3, 9

on the top of the stack I have :

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

then :

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

then :

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

Here is the stack I get :

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

find k th element :

I get 3 in O(1)

now I can pop 9 and 3 (takes O(1)):

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

find kth element :

I get 7 in O(1)

and push 0 (takes O(ln(k) - insertion)

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

Answer 5

The only actual working implementation I can wrap my head around is Push/Pop O(log k) and Kth O(1).

• Stack (single linked)
• Min Heap (size k)
• Stack2 (doubly linked)
• The value nodes will be shared between the Stack, Heap and Stack2

PUSH:

• Push to the stack
• If value >= heap root
• • If heap size < k
• • • Insert value in heap
• • Else
• • • Remove heap root
• • • Push removed heap root to stack2
• • • Insert value in heap

POP:

• Pop from the stack
• If popped node has stack2 references
• • Remove from stack2 (doubly linked list remove)
• If popped node has heap references
• • Remove from the heap (swap with last element, perform heap-up-down)
• • Pop from stack2
• • If element popped from stack2 is not null
• • • Insert element popped from stack2 into heap

KTH:

• If heap is size k
• • Return heap root value

Answer 6

What if you paired the stack with a pair of Fibonacci Heaps? That could give amortized O(1) Push and FindKth, and O(lgN) delete.

The stack stores [value, heapPointer] pairs. The heaps store stack pointers.
Create one MaxHeap, one MinHeap.

On Push:
if MaxHeap has less than K items, insert the stack top into the MaxHeap;
else if the new value is less than the top of the MaxHeap, first insert the result of DeleteMax in the MinHeap, then insert the new item into MaxHeap;
else insert it into the MinHeap. O(1) (or O(lgK) if DeleteMax is needed)

On FindKth, return the top of the MaxHeap. O(1)

On Pop, also do a Delete(node) from the popped item's heap.
If it was in the MinHeap, you are done. O(lgN)
If it was in the MaxHeap, also perform a DeleteMin from the MinHeap and Insert the result in the MaxHeap. O(lgK)+O(lgN)+O(1)

Update:
I realized I wrote it up as K'th smallest, not K'th largest. I also forgot a step when a new value is less than the current K'th smallest. And that step pushes the worst case insert back to O(lg K). This may still be ok for uniformly distributed input and small K, as it will only hit that case on K/N insertions.

*_{moved New Idea to different answer - it got too large.}

Answer 7

@tophat is right - since this structure could be used to implement a sort, it can't have less complexity than an equivalent sort algorithm. So how do you do a sort in less than O(lg N)? Use Radix Sort.

Here is an implementation which makes use of a Binary Trie. Inserting items into a binary Trie is essentially the same operation as performing a radix sort. The cost for inserting and deleting s O(m), where m is a constant: the number of bits in the key. Finding the next largest or smallest key is also O(m), accomplished by taking the next step in an in-order depth-first traversal.

So the general idea is to use the values pushed onto the stack as keys in the trie. The data to store is the occurance count of that item in the stack. For each pushed item: if it exists in the trie, increment its count, else store it with a count of 1. When you pop an item, find it, decrement the count, and remove it if the count is now 0. Both those operations are O(m).

To get O(1) FindKth, keep track of 2 values: The value of the Kth item, and how many instances of that value are in the first K item. (for example, for K=4 and a stack of [1,2,3,2,0,2], the Kth value is 2 and the "iCount" is 2.) Then when you push values < the KthValue, you simply decrement the instance count, and if it is 0, do a FindPrev on the trie to get the next smaller value.

When you pop values greater than the KthValue, increment the instance count if more instances of that vaue exist, else do a FindNext to get the next larger value.

(The rules are different if there are less than K items. In that case, you can simply track the max inserted value. When there are K items, the max will be the Kth.)

Here is a C implementation. It relies on a BinaryTrie (built using the example at PineWiki as a base) with this interface:

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

Here is the Push function.

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

Here is the helper to track the 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;
   }
}

Here is the Pop function

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

And the helper to increase the 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;
      }
   }
}

So this is algorithm is O(1) for all 3 operations. It can also support the Median operation: Start with KthValue = the first value, and whenever stack size changes by 2, do an IncreaseKth or DecreasesKth operation. The downside is that the constant is large. It is only a win when m < lgK. However, for small keys and large K, this may be good choice.

Answer 8

Use a Trie to store your values. Tries already have an O(1) insert complexity. You only need to worry about two things, popping and searching, but if you tweak your program a little, it would be easy.

When inserting (pushing), have a counter for each path that stores the number of elements inserted there. This will allow each node to keep track of how many elements have been inserted using that path, i.e. the number represents the number of elements that are stored beneath that path. That way, when you try to look for the kth element, it would be a simple comparison at each path.

For popping, you can have a static object that has a link to the last stored object. That object can be accessed from the root object, hence O(1). Of course, you would need to add functions to retrieve the last object inserted, which means the newly pushed node must have a pointer to the previously pushed element (implemented in the push procedure; very simple, also O(1)). You also need to decrement the counter, which means each node must have a pointer to the parent node (also simple).

For finding kth element (this is for smallest kth element, but finding the largest is very similar): when you enter each node you pass in k and the minimum index for the branch (for the root it would be 0). Then you do a simple if comparison for each path: if (k between minimum index and minimum index + pathCounter), you enter that path passing in k and the new minimum index as (minimum index + sum of all previous pathCounters, excluding the one you took). I think this is O(1), since increasing the number data within a certain range doesn't increase the difficulty of finding k.

I hope this helps, and if anything is not very clear, just let me know.