waipoli's blog

Data structure question
By waipoli, history, 6 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

»
6 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
»
6 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
»
6 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
  • »
    »
    6 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
    • »
      »
      »
      6 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
  • »
    »
    6 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
»
6 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
»
6 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