Data structure for fast insertion/deletion with sorting

I'm desperately looking for a data structure allowing me to perform a good amount of insertions, almost as many deletions (probably same order of magnitude) and a very quick lookup of the highest (or the lowest, can live with either) value. The deletion will always only affect the highest (or, again, lowest) value. The problem is that the values have to be sorted and at any moment I could insert an element going at any point between other two. The only value I want to read (and delete) q开发者_运维问答uickly, at any point is the maximum (or, again, minimum).

Is there anything you recommend?

Please give algorithmic complexity analysis for your proposed answers.

---

Loos like you need a Max-Heap.

Supports O(log n) insertion, O(1) lookup of maximum and O(log n) deletion of maximum.

---

A heap is what you want. Here's a simple implementation of a binary heap. Whether it's a max heap or min heap depends on the comparison function you pass to it: http://www.informit.com/guides/content.aspx?g=dotnet&seqNum=789

Note that a binary heap isn't the only way to build a heap. But it's likely the easiest to build, and it performs well enough in most situations.

The items in the heap are not sorted, although they're ordered. The only guarantee is that the highest (lowest) item is at the top of the heap and will be the one retrieved when you ask for the next item.

What you're building sounds like a priority queue. There are other ways to implement a priority queue. For example, I've seen a skip list based priority queue that outperforms a heap-based priority queue.

If you really need O(1) insertion, then look into something like the Fibonacci heap.

---

This data structure is called self-balancing binary search tree, and it's implemented in every language I used, except Borland Pascal.
Cost for all operations you mentioned (add/delete/lookup) is O(logn). Min-max lookup can be O(1) too.

You can traverse all elements in sorted order in O(n).

edit
I wasn't suggesting heap, because it doesn't satisfy "have to be sorted" requirement.

If you need to insert/delete/lookup only max, then I would suggest sorted array or linked list. Max insertion/deletion/lookup O(1) and all elements are already sorted.