4

I have fifo query where I put and eject doubles. After each update I need max and min values. I don't need position (or index) of these values in query. How to do that effectively? log(N) or probably even O(1)?

upd: found this Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations

Community
  • 1
  • 1
Oleg Vazhnev
  • 23,239
  • 54
  • 171
  • 305
  • If you want to keep track of the largest and smallest values in a stack, at each update, then there will be two calculations done on each update and thus have O(n) time. – Rey Gonzales Jul 19 '12 at 18:43
  • @ReyGonzales O(N) is too much calculations. There must be something better. – Oleg Vazhnev Jul 19 '12 at 18:44
  • 2
    If you're checking n elements, then you'll have O(n) time no matter what. – Rey Gonzales Jul 19 '12 at 18:45
  • 1
    @ReyGonzales I don't need to check n elements always obviosly. In most situations max and min doesn't change at all and I don't need to check anything at all as removed element is neither max nor min – Oleg Vazhnev Jul 19 '12 at 18:49
  • Although your max or min may not change at an update, you will still need to compare the newest value to the max and/or min. – Rey Gonzales Jul 19 '12 at 18:51
  • I think you're mixing up ONE insert on a list on N and N inserts on a list of N. – Wug Jul 19 '12 at 20:43
  • Actually, what I meant was adding a check() that is O(1) time on each update will effectively be O(n) on n updates. – Rey Gonzales Jul 19 '12 at 21:23

2 Answers2

3

This is a tricky question. Consider the following:

Say the size of your fifo at any given time is N. Say that you track the min and max with just a pair of floats. Say that the size of the fifo remains reasonably constant.

We can therefore assume that one "operation" on the queue logically consists of one push and one pop.

Say you are comparing 2 methods of handling this: one uses a heap pair and one that uses a naive compare and search.

For the heap method:

Each operation, you push to the list and both heaps, then pop from the list and both heaps. The heap operations are always O(log(n)) and the list operation is O(1), so as N is large, the time complexity of one operation is O(log(N)) average case. It's important to note that the heap operations are always this complexity regardless of whether or not the currently popped element is a min or max element. Thus, N operations has a time complexity of O(N*log(N)).

For the naive method:

Each operation, you push and pop the list, and compare the popped item to the stored min and max. If the item is the same as either one, you search the list either for an item of equal value (in which case you break early) or otherwise through the entire rest of the list, until you find the next best element. You then update the min/max with the next best. This method has O(1) typical case and O(N) worst case (min or max needs an update). It's important to note that for some range of N numbers the number of times you will need to update min and max goes to a constant, and the number of times you won't goes to N. Therefore, N operations has a time complexity of O(N). The naive case is actually better than a more advanced solution.

That said, I don't think heaps can efficiently remove elements, so you'd run into lots of trouble that way.

Thus, consider the following pseudocode:

queue fifo;
float min, max;

void push(float f)
{
    if (fifo.size == 0)
    {
        min = f;
        max = f;
    }
    else if (f > max) max = f;
    else if (f < min) min = f;

    fifo.push(f);
}

float pop()
{
    if (fifo.size == 0) return (*((float *)NULL)); // explode
    float f = fifo.pop();
    if (fifo.size == 0)
    {
        min = NaN;
        max = NaN;
        return f;
    }
    if (f == max) search_max(fifo);
    if (f == min) search_min(fifo);
    return f;
}

search_max(queue q)
{
    float f = min;
    for (element in q)
    {
        if (element == max) return;
        if (element > f) f = element;
    }
    max = f;
}

search_min(queue q)
{
    float f = max;
    for (element in q)
    {
        if (element == min) return;
        if (element < f) f = element;
    }
    min = f;
}
Wug
  • 12,956
  • 4
  • 34
  • 54
  • imaging that I have always growing numbers. so I always pop smallest one. so I have to research every time and so I have O(N*N) in worst case. i'm sure there should be better algorithms. however I agree with you and between this two I will select naive one. – Oleg Vazhnev Jul 19 '12 at 19:58
  • If you know for certain that your data set is ordered, you can do one of a few things: 1) optimize for the ordering 2) randomize insert order. You could cheat at it by adding the first element (the smallest) and then the last (the largest) and then all of the elements between would never trigger the lookup. – Wug Jul 19 '12 at 20:40
0

How about using heap ( http://en.wikipedia.org/wiki/Heap_%28data_structure%29 ). You can have two heaps. One for extracting min and one for max (as a single heap cannot extract min and max at the same time). it also does not require any space overhead and the Big O is log n.

mu_sa
  • 2,685
  • 10
  • 39
  • 58