CODEWITHSUNDEEP
algorithmsortingdata-structures
lee
lee

Reputation: 772

Data structure with fast sorted insertion, sorted deletion and lookup

I'm looking for a very specific data structure. Suppose the maximum number of elements is known. All elements are integers. Duplicates are allowed. The operations are:

Look up. If I inserted n elements, a[0] is the smallest elements, a[a.length - 1] is the highest. a[k] is the k smallest element. Required runtime: O(1)

Insertion. Does a sorted insertion, insert(b) where b is an integer. Required runtime: O(log n)

Deletion. delete(i) deletes the ith element. Required runtime: O(log n)

I want kind of data structure is this? My question is language independent, but I'm coding in C++.

Upvotes: 1

Views: 1264

Answers (1)

Fureeish
Fureeish

Reputation: 13424

I believe such data structure does not exist. Constant lookup for any element (e.g. indexing) requires contiguous memory, which makes insertion impossible to do in less than O(n) if you want to keep the range sorted.

There are arguments for hash tables and wrappers around hash tables, but there are two things to keep in mind when mentioning them:

  • Hash tables have average access (insertion, deletion, find) in O(1), but that assumes very few hash collisions. If you wish to meet the requirements in regard to pessimistic complexities, hash tables are out of the quesion since their pessimistic access time is O(n).

  • Hash tables are, by their nature, unordered. They, most of the time, do have internal arrays for storing (for example) buckets of data, but the elements themselves are neither all in contiguous memory nor ordered by some property (other than maybe modulo of their hash, which itself should produce very different values for similar objects).

To not leave you empty handed - if you wish to get as close to your requirements as possible, you need to specify which complexities would you sacrifice to achieve the others. I'd like to propose either std::priority_queue or std::multiset.

  • std::priority_queue provides access only to the top element - it is guaranteed that it will be either the smallest or the greatest (depending on the comparator you use to specify the relation) element in the collection. Insertion and deletion are both achieved in O(log_n) time.

  • std::multiset* provides access to every element inside it, but at a higher cost - O(log_n). It also achieves O(log_n) in insertion and deletion.

*Careful - do not confuse with std::set, which does not allow for duplicate elements.

Upvotes: 4

Related Questions