Jump to content
  • Advertisement
Sign in to follow this  
TheHoff

Data structure question

This topic is 4705 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need a data structure that contains a bunch of sorted keys. I'd like insertion and deletion to be pretty fast -- better than linear time. I should also be able to update the keys pretty quickly while maintaining the sorted-ness of the structure. What do you guys think? It sounds to me like a heap is pretty close. The canonical heap implementation does not allow arbitrary deletion, but I guess that can be faked pretty easilyby forcing it to be the max and removing (after re-heapifying). Assuming that updating a key and then walking it up/down the heap would work, which it seems like it would. Does anyone have any suggestions?

Share this post


Link to post
Share on other sites
Advertisement
A heap doesn't actually maintain a sorted order, so it doesn't really fit your description. With a balanced binary tree, finding, removing and adding back in an element will be O(lg n).

Share this post


Link to post
Share on other sites
I have to ask before I can even assess this problem: what will you be using said data structure for, what do you intend to store in it, what do you intend on sorting by?

The immediate thought that came to mind was "This man is writing an SQL server" and I got a bit of a chuckle, but yeah, it would help to know what you're hoping to store in said container.

Share this post


Link to post
Share on other sites
I'm experimenting with LOD algorithms -- I'd like to be able to order nodes by how large their rendering error is, which is view-dependent and hence requires a data structure that can be updated quickly. I've gone ahead with the binary tree: I liked the idea of a heap because the canonical implementation allows inserting the same key several times. I know there's always std::multimap, but I'm not using C++. My language of choice (Scheme) has surprisingly little available in the way of data struct libraries so I was just wondering what people around here thought about the problem.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!