4

I have a collection, I don't know which data structure to use yet for this. I have two functions, add and remove.

Both of the functions need to have similar complexities because they both are as frequently used.

It's either add function will be simple as O(1) and removeMax will be O(log n) or both o(1) or one of them log n and other o(n).

removeMax should remove the maximum value and return it, and should be able to use it multiple times, so the next time u call it it removes the next new max value.

Is there a way to do both with O(1) or atleast log n for remove?

Muhammad usman
  • 521
  • 1
  • 3
  • 16
Ben Beri
  • 1,101
  • 4
  • 23
  • 64
  • The collection is, and must be, unsorted presumably? – Michael Mar 26 '19 at 08:47
  • @Michael yes it is unsorted, randomly – Ben Beri Mar 26 '19 at 08:47
  • 2
    Are you looking for Fibonacci heap (or other kind of max heap)? https://en.wikipedia.org/wiki/Fibonacci_heap - O(1) insert, O(logn) delete (amortized of course) – Ondra K. Mar 26 '19 at 08:48
  • 1
    Have a look at min-max heap. I believe that Priority queue uses one of these internally. – Michał Krzywański Mar 26 '19 at 08:48
  • [Maybe useful](https://stackoverflow.com/q/6273833/5515060), regarding the comment from @OndraK. – Lino Mar 26 '19 at 08:54
  • You can go fo red black data structure, [wiki link](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) . In java `TreeMap` is implemented using the same datastructure , so It will give you log(n) for remove and adding. [Oracle docs for treemap](https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html) – RAHUL ROY Mar 26 '19 at 09:03

3 Answers3

4

If it's a sorted structure (such as TreeSet), both add and remove would require O(logN).

If it's not sorted, add can be implemented in O(1) but removeMax would take O(N), since you must check all the elements to find the maximum in an unsorted data structure.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • Does TreeSet automatically sorts your collection? What is its a TreeSet where Variable has getValue of integer, will it automatically know how to sort it? – Ben Beri Mar 26 '19 at 09:01
  • 1
    @BenBeri Yes it does. If the element type of the TreeSet implements Comparable, that would define the ordering. Otherwise, you can supply a Comparator to the TreeSet constructor, which will define the ordering. – Eran Mar 26 '19 at 09:03
  • @BenBri you will get sorting at the time of insertion itself, So you don't have to worry about much at that time( It will take worst case scenario O(nlogn) for insertion instead of O(n) for you entire input for first time after that every insertion deletion followsO(logn). But please keep in mind that tree set will discard duplicate elements. – RAHUL ROY Mar 26 '19 at 09:14
0

Max heaps are probably what you are looking for, their amortized complexity of remove operation is O(logn). Fibonacci heap (see this great animation to see how it works) seems like the data structure suitable for you, as it has O(1) for insert and all other operations. Sadly, it's implementation is not a part of standard Java libraries, but there's ton of implementations to be found (for instance see the answer in the comment from @Lino).

Guava's implementation of min-max heap

Ondra K.
  • 2,767
  • 4
  • 23
  • 39
0

If you need a data structure to do both add() and removeMax() in O(logn), then you just need a sorted array. For both removeMax() and add(), you can use binary search to find the target value. (for remove, you find the max value. for add, you find the biggest value smaller than the one you want to insert, and insert the value after it).Both time complexity is O(logn).

Meng Tim
  • 408
  • 1
  • 6
  • 19