Double Ended Priority Queue?

DeadBankClerk

Does anyone have an ideas on a good data structure with which to implement a double ended priority queue?

By double ended i mean ability to remove the items with highest and lowest priorities.

I was thinking of implementing it with a sorted linked list which could be sorted using quicksort (if it needs sorting at all) and items could be added using binary search?

Nodes in the queue will be:

[php]
class PriorityNode
{
public:
int priority;
Triangle* data;
}
[/php]

satchmo

Yeah, a linked list with pointers to both the head and the tail seems like a good way to go. I wouldn't recommend going with quicksort for this though, especially if it's for some sort of polygon LOD algorithm, where time would be critical. Since the list will already be mostly sorted, insertion sort will give you some significant speed gains over quicksort.

DeadBankClerk

I've gone with a binary tree for now, but i can change it easily and still retain the same interface.

As you guessed I am making an LOD terrain engine*.

Adding to the tree will be Order (Log n). I am hoping to do a non-recursive inorder (or reverse inorder) traverse of the tree, leaving it intact as i traverse it (ie, not deleting nodes) and deleting it after.

The roam algorithm uses two priority queues, one for merging one for spliting triangles to get the desired level of detail, but as far as I can see, the split priority queue will be the inverse of the merge priority queue, hence the double ended queue im toying with.

I have the TriBinTree spliting away, but i can get the merge operation to work

here's a pic of what i have so far:


Note the heightmap values are generated by rand % 20 in this picture, hence the lack of resemblence to terrain. The splits are called on the left-most leaf in the BinTriTree each time, as i have to get the priority queue coded before i can implement line-of-sight spliting/merging.

Time to go to bed and read about to to do fulstrum culling rapidly.

* Implementing ROAM.

satchmo

You've probably already read it, but there's a good article on implementing ROAM on Gamasutra. It's from a year or two ago though so you might have to go digging.

DeadBankClerk

Went away for the summer
Started up on my project a few weeks ago I've almost got it all working now. Im trying to speed the code up now.

satchmo

hehe i was wondering who dredged this thread up

Excellent, looks good (nice texture) - looking forward to seeing a demo.