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?

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).

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.

AVL-trees, red-black-trees, b-trees, b*-trees or judy arrays all fit your requirements.

I would use std::set in C++

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.