Data structure for quick insertion / deletion with sorting

Question

I am desperately looking for a data structure that allows for a large number of attachments, almost as many deletions (probably of the same order), and a very quick search for the highest (or lowest) can live with) cost. Deletion will always affect only the highest (or, again, the 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 the other two. The only value that I want to read (and delete) quickly, at any time, is the maximum (or, again, the minimum).

Is there anything you recommend?

Please provide an algorithmic complexity analysis for your suggested answers.

Answer 1

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

Note that a binary heap is not the only way to create a heap. But this is most likely the easiest to build, and in most cases it works quite well.

Items in the heap are not sorted, although they are ordered. The only guarantee is that the highest (lowest) item is at the top of the heap and will be the one that was received when the next item was requested.

What you are building sounds like a priority queue . There are other ways to implement the priority queue. For example, I saw a priority-based skip list that exceeds the heap priority queue.

If you really need an O (1) insert, look at something like a Fibonacci heap .

Answer 2

Loos, as you need Max-Heap .

Input support O (log n), O (1) search for maximum value and O (log n) delete maximum value.

Answer 3

This data structure is called a self-balancing binary search tree , and it is implemented in all languages ​​that I used except Borland Pascal.
The cost of all the operations you specify (add / remove / search) is O(logn) . Minimal search can be O(1) too.

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

change
I did not offer a bunch, because it does not satisfy the "need to sort" requirements.

If you need to insert / delete / find only max , I would suggest a sorted array or linked list. Max. Insert / delete / search O(1) and all items are already sorted.