CODEWITHSUNDEEP
pythonalgorithmdata-structures
Nahuel Almeira
Nahuel Almeira

Reputation: 57

Insert and get max from structure in constant time

I need a data structure to store positive (not necessarily integer) values. It must support the following two operations in sublinear time:

  1. Add an element.
  2. Remove the largest element.

Also, the largest key may scale as N^2, N being the number of elements. In principle, having O(N^2) space requirement wouldn't be a big problem, but if a more efficient option exists in terms of store, it would work better.

I am working in Python, so if such a data structure exists, it would be of help to have an implementation in this language.

Upvotes: 0

Views: 806

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Although constant time may be impossible, depending on your input constraints, you might consider a y-fast-trie, which has O(log log m) time operations and O(n) space, where m is the range, although they work with integers, taking advantage of the bit structure. One of the supported operations is next higher or lower element, which could let you keep track of the highest when the latter is removed.

Upvotes: 0

ddfra
ddfra

Reputation: 2565

the best data structure you can choose for this operations is the heap: https://www.tutorialspoint.com/python_data_structure/python_heaps.htm#:~:text=Heap%20is%20a%20special%20tree,is%20called%20a%20max%20heap.

with this data structure both adding an element and removing the max are O(log(n)).

this is the most used data structure when you need a lot of operations on the max element, for example is commonly used to implement priority queues

Upvotes: 1

Tim Peters
Tim Peters

Reputation: 70735

There is no such data structure. For example, if there were, sorting would be worst-case linear time: add all N elements in O(N) time, then remove the largest element remaining N times, again in total O(N) time.

Upvotes: 2

Related Questions