performancealgorithmsortingsortedcollection

Maintaining sort while changing random elements


I have come across this problem where I need to efficiently remove the smallest element in a list/array. That would be fairly trivial to solve - a heap would be sufficient.

However, the issue now is that when I remove the smallest element, it would cause changes in other elements in the data structure, which may result in the ordering being changed. An example is this:

I have an array of elements:

[1,3,5,7,9,11,12,15,20,33]

When I remove "1" from the array "5" and "12" get changed to "4" and "17" respectively.

[3,4,7,9,11,17,15,20,33]

And hence the ordering is not maintained.

However, the element that is removed will have pointers to all elements that will be changed, but there is not knowing how many elements will be changed and by how much.

So my question is:

What is the best way to store these elements to maximize performance when removing the smallest element from the data structure while maintaining sort? Or should I just leave it unsorted?

My current implementation is just storing them unsorted in a vector, so the time complexity is O(N^2), O(N) for finding the smallest element, and N removals.


Solution

  • A.

    If you have the list M of all changed elements of the ordered list L,

    B.

    If you are sure that new elements are few and not strongly changed, simply use the bubble sort.