Maintaining sort while changing random elements

Question

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.

Answer 1

A.

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

• go through M, and for every element

• If it is still ordered with its neigbours in M, live it be.

• If it is not in order with neighbours, exclude it from the M.

• Such excluded elements will create a list N

• Order N

• Use some algorithm for merging ordered lists. http://en.wikipedia.org/wiki/Merge_algorithm

B.

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

Answer 2

I would still go with a heap ,backed by an array

In case only a few elements change after each pop,After you perform the pop operation , perform a heapify up/down for any item that reduces in value. It will still be in the order of O(nlog k) values, where k is the size of your array and n the number of elements that have reduced in size.

If a lot of items change in size , then you can consider this as a case where you have an unsorted array and you just create a heap from the array.