Is there a specific algorithm that allows me to maintain min / max in a small / medium sized sliding window (the typical size is 600, with all the elements being integer)? The window is indeed the last N observations in the stream. So, I add a new observation and delete the oldest observation at every point in time, so I would like to save min and max over the last N tricks.
This is another problem from the one specified in the minimal sliding algorithm, because I do not support all the data, and therefore the index-based solution will not be applicable here. Moreover, my input will be in a circular array.
Heaps probably won't work too well: I'm not deleting / adding a Min / Max element, but the oldest element that will destroy the goal of having a heap first.
log (n) complexity-based structures, such as red-black trees, will work very well, and layout trees may be even more suitable for the type of data that I would have, but whether they are too redundant the size with which I had business?
source
share