waipoli's blog

Data structure question
By waipoli, history, 10 months ago, In English

Hello codeforces!

Recently in the problem I came across with this data structure, which can perform this operations:

  • add element

  • delete element

  • return the maximal of it

with O(1) for query.

So the question is simple: is it exist?

  • Vote: I like it
  • -27
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Auto comment: topic has been updated by waipoli (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Auto comment: topic has been updated by waipoli (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

You can use heap but it is O(log n) for each. I think it is the best for your need.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I have forgot to mention that i'm happy with offline solution

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Offline approach where you have addition and deletion?? Is it possible?

      → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Doesn't set do same thing or am I missing something?

    → Reply
»
10 months ago, # |
  Vote: I like it +57 Vote: I do not like it

No. Consider there exists some ds which perfoms given operations in O(1). Suppose I insert N elements.

Further I would store current maximal element (say in an array) and delete it in O(2) and continue this process N times. The resultant vector would contain sorted elements in effective time of O(3N) which is not possile.

(It can be proved worst case time complexity of sorting an array cannot be less than NlogN.)

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can write a Fibonacci's heap, which can add element and get min/max in $$$O(1)$$$. But it can delete only in $$$log(n)$$$ time

→ Reply
»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

You can use soft heap. It can add element or delete minimum ( and some other operations ) in O(1), but not delete some elements. Deleting I see as memorizing number of elements in some hashset and when we have x as minimum and number of x in that hashset is 0, we can say that it is minimum ( for maximum multiply all numbers by -1 ) and otherwise decrease it's number from hashset and perform operation one more time. The only issue there that the elements can be corrupted. You choose some E and then you can performe operations in O(log(1/E)) time and at most E*n out of n elements are corrupted. It is even more complicated them Fibonacci's heap.

→ Reply