How to track max / min request fifo

Question

I have a fifo request where I put and pop the doubles. After each update, I need the max and min values. I do not need the position (or index) of these values ​​in the request. How to do it efficiently? log (N) or maybe even O (1)?

upd: found the implementation of the queue in which push_rear (), pop_front () and get_min () are all constant-time operations

Answer 1

This is a difficult question. Consider the following:

Say that the size of your fifo at any given time is N. Say that you track min and max only with a pair of floats. Let's say that the fifo size remains fairly constant.

Thus, we can assume that one “operation” in the queue logically consists of one click and one pop function.

Suppose you are comparing 2 methods of handling this: one that uses a bunch of pairs and one that uses naive comparison and search.

For the heap method:

Each operation, you click on the list and both heaps, and then drop out of the list and both heaps. The heap operations are always O (log (n)), and the list operation is O (1), since N is large, the time complexity of one operation is O (log (N)) the average case. It is important to note that heap operations are always such complexity, regardless of whether the current poped element is minimum or maximum. Thus, N operations has a time complexity of O (N * log (N)).

For the naive method:

Each operation, you click and publish the list, and compare the pop-up element with the saved minimum and max. If the item is the same as one, you search the list for either an item with the same value (in this case, you will break early) or otherwise through the rest of the list until you find the next best item. Then you update min / max with the next best. This method has an O (1) typical case and O (N) the worst case (min or max needs to be updated). It is important to note that for a certain range of numbers N the number of times you need to update min and max goes to a constant, and the number of times you do not go to N. Therefore, N operations have the time complexity of NA). A naive case is actually better than a more advanced solution.

However, I don't think heaps can remove elements efficiently, so you will run into a lot of trouble this way.

Thus, consider the following pseudo-code:

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

Answer 2

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 (since one heap cannot extract min and max at the same time). it also does not require any additional overhead, and Big O - log n.