Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Double ended priority queue

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)

like image 417
Martin Avatar asked Jul 01 '09 11:07

Martin


People also ask

What is difference between priority queue and double-ended queue?

Priority Queue In this queue, the enqueue operation takes place at the rear in the order of arrival of the items, while the dequeue operation takes place at the front based on the priority of the items.

What is double-ended queue with example?

Also, you will find working examples of different operations on a deque in C, C++, Java and Python. Deque or Double Ended Queue is a type of queue in which insertion and removal of elements can either be performed from the front or the rear. Thus, it does not follow FIFO rule (First In First Out).

Why double-ended queue is used?

Deque is a double-ended queue that allows us to add/remove elements from both the ends i.e. front and rear, of the queue. Deque can be implemented using arrays or linked lists. However, we also have a Standard Template Library (STL) class which implements the various operations of the Deque.

What are the types of double-ended queue?

There are two types of deques. These two types are due to the restrictions put to perform either the insertions or deletions only at one end. They are, (i) Input-restricted deque (ii) Output-restricted deque.


1 Answers

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.

like image 55
Firas Assaad Avatar answered Sep 20 '22 14:09

Firas Assaad