Sorted structure with fast insertion and head/floor removal many elements

user_10528516 0
Viewed 38

What is the fastest sorted structure for insertions and removal many elements higher/lesser or equal to given value? I will describe it in few steps:

  1. Starting point = [1,2,3]
  2. New value 5 = [1,2,3,5]
  3. Next new value 4 = [1,2,3,4,5]
  4. Next new value 4 again = [1,2,3,4,4,5] (4's are treated the same)
  5. removeTail(4) = [1,2,3] (it returns removed elements: [4,4,5]
  6. removeHead(2) = [3] (it returns removed elements: [1,2]

The structure will be accessed from single thread, memory consumption doesn't matter. I would like to achive the fastest (at least O(logN)) complexity. I wonder if I should use some B-Trees but it seems like too much re-balancing overhead so maybe instead I should try skip-list?

data-structures algorithm
1 Answers

If you are OK with likely O(logn) performance for each of these operations, a simple probabilistic skip list sounds perfect here.

Insertion and deletions are native to Skip List.

RemoveTail() and RemoveHead() are simply finding the element, and trimming everything "above it" (and by above it, I mean the actual path you used to find the element) to the left or to the right. Each such operation is O(logn) on average, as you touch only the nodes in the path (and maybe one adjacent for each of them).

If you want deterministic - this could be done as well, but will be more complicated to remove elements and rebalance while keeping deterministic structure, though not impossible.

user_5726700
Related