CODEWITHSUNDEEP
algorithmdata-structures
sebas
sebas

Reputation: 1085

Which data structure should I use to have fast deletion/insertion and max (or min) search?

I am looking for a data structure that could ensure at least Log(n) complexity for deletion and insertion of a node and something close to O(1) or amortized Log(n) to search the maximum (or minimum) value.

I was thinking to use a self-balanced BST (which one?) modified to sort of remember the maximum (or minimum) value inserted.

Any suggestion?

Sorry I have to edit the question...of course a self-balanced BST can allow to search max and min in log(n), but I was thinking about something more toward O(1).

Upvotes: 3

Views: 4613

Answers (5)

Jim Mischel
Jim Mischel

Reputation: 134125

I'd use a skip list for this. You'd have to make a slight modification to add a tail pointer, but beyond that it does everything you want. With the modification:

  • Find first is O(1)
  • Remove first is O(1)
  • Find last is O(1)
  • Remove last is O(1)
  • Find arbitrary node is O(log n)
  • Delete arbitrary node is O(log n)

Skip list is not much more difficult to implement than a binary heap and, as I recall, a whole lot easier than implementing a balanced binary tree. I was able to implement it from the original paper, which has a much better description than most scholarly papers I've seen.

Upvotes: 1

Erik P.
Erik P.

Reputation: 1627

The comments already discuss a double-ended heap, and conclude that it is not suitable because deletion requires knowing the position of the element. I believe this can be fixed, at a cost that is reasonable in many scenarios, as follows: Maintain two double-ended heaps, one (say A) of entries entered into the set and one (say B) of entries deleted.

  • To insert an element into the set, insert it into A.
  • To delete an element from your set, insert into B.
  • To get the maximum of your set: if B is empty, just return the maximum of A. Otherwise, let mA be the maximum of A and mB of B. If mA > mB, then mA was not deleted and you can return it. If mA = mB, then it was deleted and you should pop mA from A and mB from B, then start from the beginning of this bullet point. You cannot have mA < mB.
  • To get the minimum of your set, adapt the procedure for maximum in the obvious way.

This will give you O(log(k)) insertion and deletion, and amortized O(1) minimum / maximum computation. However, k in this case is the number of elements that were inserted into your set and have not yet been popped from both A and B; the more obvious other solutions have complexities depending on the number of elements actually in the set (i.e., elements that were inserted and not yet deleted) - let's call this number n. You could come up with scenarios where k is so much greater than n that this is not competitive with the other solutions -- and other scenarios where k and n are roughly equal and this solution is faster. So it depends on your application whether this is a good idea or not.

Upvotes: 0

Trying
Trying

Reputation: 14278

You can use red-black tree or AVL tree.

Here finding the min-max, and deleting a node are O(LogN).

According to the latest edit of the question i can suggest you to data structures which can give you O(1) min/ max, insertion and Deletion in O(1) by modified Stack. If interested I can proceed. It all depends on your needs, how frequently you want to find min/max, where you want to insert, which particular element to delete all these.

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55649

You can use just about any self-balancing BST (e.g. red-black, AVL).

If you keep track of the minimum and maximum, the queries to get them will take O(1).

Since the minimum and maximum can only change on insertions and deletions, you can essentially just redetermine it (in O(log n)) when doing those operations (the running time of them will still be O(log n)).

Though it's probably a better idea to just redetermine the minimum or maximum when you receive a query for it and there was an insert or delete since the last query.

It's also possible to be more intelligent about it - if you've only gone left thus far, you're at the minimum, if you've only gone right, you're at the maximum. When inserting, just replace the minimum / maximum if appropriate. When deleting, just look around in the tree from the deleted node to find the new minimum / maximum.

Upvotes: 6

MariaJ
MariaJ

Reputation: 11

An AVL would suit: Searching for max and min is O(log n) since the min is the left-most node and the max is the right-most node and the tree is balanced. If you are only deleting the max/min nodes this is also O(log n) but only when deleting the node makes the tree unbalanced.

Upvotes: 1

Related Questions