Keep track on biggest element in FIFO queue

Question

Problem

I have fixed length FIFO queue of integer values.
Everytime I push new value into it, oldest one is removed.
Queue must be able to tell, after every insertion & removal operation, what is currently the biggest value in it.

Question

Is there algorithm better than doing loop over all queue elements every time?

After accept update

Because of limited domain of integers in my application, I was also thinking about sparse histogram, containing counts of given value in my queue. So every time value arrives I increment its value in histogram, and decrement when given value is removed. Then to get max/min I need only to get first/last histogram index with non zero count.

same question? http://stackoverflow.com/questions/11567180/how-to-track-max-min-of-fifo-query — Irit Katriel, Nov 27 '14 at 12:07

Niklas B. · Accepted Answer · 2014-11-27T15:25:32.667

In fact due to the specific structure of the problem this is possible with O(1) amortized operations, which is much better than using a max-heap. An application is the sliding window minimum algorithm. Essentially you keep a second queue that contains the decreasing subsequence of all the suffix maxima:

queue = new Queue()
mono = new Queue()
cnt = 0

def enqueue(x):  # O(1) amortized
  while !mono.empty() and x >= mono.back()[1]:
    mono.pop_back()
  queue.push_back([x, cnt])
  mono.push_back([x, cnt])
  cnt++

def dequeue():   # O(1) 
  if mono.front()[0] == queue.front()[0]:
    mono.pop_front()
  return q.pop_front()

def max():  # O(1)
  return mono.front()[1]

Thanks, this is what I was thinking of. – Anonymous Nov 27 '14 at 17:09 — Anonymous, Nov 27 '14 at 17:09

score 1 · Answer 2 · answered Nov 27 '14 at 12:10

1

Isn't this just a trade off between storage and speed. So if you were willing to store a tree sorted by size whose element were pointed to by the elements in the FIFO when elements were added to the FIFO a companion element would be added to the tree sorted on size. Likewise when you deleted an element from the FIFO the element removed would also be pulled from the tree.

answered Nov 27 '14 at 12:10

Matthew V Carey

196
1
10

'+1' Exactly, seams like I need to keep elements linked to both structures. – Anonymous Nov 27 '14 at 12:12

Keep track on biggest element in FIFO queue

Problem

Question

After accept update

2 Answers2