Algorithm to update priority ordered list where changing priority of an item is expensive

algorithms

I am working against an API where I can add and update items in a list that is ordered by a priority field I can set (which need not be contiguous but must be a positive integer).

Updating a list member is an expensive operation, so I want to minimise the number of updates.

What I want is an algorithm that will minimise the number of updates required when the list is reordered.

i.e. The worst case scenario for this is to use contiguous priorities starting at 1. e.g.

Priority  | item
----------------
1           A
2           B
3           C
4           D
5           E

In this case to move item E to the top of the list, every single item would need to have its priority updated.

The naive solution I have though of is to implement large numbers for priorities, and put in priorities that are half way through the interval between two items when an item needs to be placed there.

e.g.

Priority  | item
----------------
1000000     A
2000000     B
3000000     C
4000000     D
5000000     E

In this case to move E to the top only one update is required (and I can set its priority to 500000)

The issue with this is that it will act like a binary search, and even in the case of using starting numbers of the order of 10^9 it will only take 30 operations until the priorities could become contiguous.

Is there a better algorithm than this? Is there an existing one I can use (but have not found via google), or can someone suggest an improvement to this?

Best Answer

If you're stuck with your list data structure

If you strive purely to minimize number of priority updates, there's not too much you can do beyond the binary-search approach.

Otherwise, one possible smallish improvement I can think of is, whenever you insert an item C between B and D, check the item A to the B and E to the right of D and redistribute their priorities.

So for something like:

        C
        ↓
A B           D E
0 1           7 8

You'd end up with:

A   B   C   D   E
0   2   4   6   8

Note that A and E don't change, their priorities are just required in the calculation.

Or you can leave B where it is and only update D, or vice versa, depending on whether A and D or B and E are further apart.

If you can pick another data structure

It would be better to pick one where the priority is structurally defined, not explicitly for each element.

A modified balanced binary search tree could work here, where you store the number of ancestors for each node.

The comparison for insertion would then be defined purely on where you want to insert it compared with the counts of each node.

Note that something like a red-black tree doesn't require any comparisons to keep itself balanced.

Update, insert and delete operations will all take O(log n).

Depending on your requirements, you can have a secondary data structure that allows you to look up some node for a given element.

Related Topic