2

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?

  • You could use a linked list instead of the priority field. Then you would have to change at most 2 items. – Patrick Oct 8 '13 at 13:57
  • Is there anything stopping you from using a heap data structure, like most priority queue implementations? – JasonTrue Oct 8 '13 at 14:03
  • Unfortunately I can't change the API, I am just trying to implement a client to the API. – DanSingerman Oct 8 '13 at 14:06
  • @DanSingerman But can you write a heap to wrap the existing API and maintaining your own priorities and just referencing the objects in your heap? – Steven Evers Oct 9 '13 at 22:03
5

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.

  • 1
    I definitely think the "Insert and push away" idea is the best option. At most, it means you have two update operations, and for a large enough set of priority numbers, it makes it next to impossible to end up with contiguous numbers. – Bobson Oct 8 '13 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.