Double ended priority queue

Question

I have a set of data and I want to find the biggest and smallest items (multiple times), what's the best way to do this?

For anyone interested in the application, I'm developing a level of detail system and I need to find the items with the biggest and smallest screen space error, obviously every time I subdivide/merge an item I have to insert it into the queue but every time the camera moves the entire dataset changes - so it might be best to just use a sorted list and defer adding new items until the next time I sort (since it happens so often)

Answer 1

You can use a Min-Max Heap as described in the paper Min-Max Heaps and Generalized Priority Queues:

A simple implementation of double ended priority queues is presented. The proposed structure, called a min-max heap, can be built in linear time; in contrast to conventional heaps, it allows both FindMin and FindMax to be performed in constant time; Insert, DeleteMin, and DeleteMax operations can be performed in logarithmic time.