Dictionary with priorities

Question

I have a class Item and a dictionary of Items. Each item in the dictionary has a unique priority (1 to N). When I remove an item from dictionary, all other priorities are updated. I want to implement some increase/decrease priority in the dictionary. If I want to increase the priority of a single item I swap priorities with the next lower item. The problem is increasing priorities of a collection of items

public class Item
{
    public string key;
    public string data;
    public int Priority;
}

Dictionary<string, Item> allItems = new Dictionary<string, Item>();

public void AddToQueue(Item item)
{
    item.Priority = allItems.Count + 1;
    allItems[item.key] = item;
}

public void PriorityUp(Item it)
{
    if(it.Priority <= 1)
        return;

    it.Priority--;

    foreach(var item in allItems )
        if(item.Value.Priority == it.Priority)
        {
            item.Value.Priority++;
            break;
        }
}

public void PriorityUp(IEnumerable<Item> items)
{
    //TODO
}

I have dictionary in order to find efficiently an item. Increasing priority of some items must create some change in priorities of others

To be more clear: I have a collection of N items (list, array, dictionary...) I choosed dictionary because I must do some other operations also. Each item has a field Priority with some unique value 1<=P<=N.

I want to find the resulted Priority (1 to N) of all items when I select some and increase/decrease P.

What are you trying to do with the data? Maybe this should just be a priority queue and not a dictionary. — bengoesboom, Sep 17 '13 at 15:06
@BartoszKP Increasing priority of some item ,may change the priority of next whose I want to increase — albert, Sep 17 '13 at 15:16
Well yes, but this is exactly what happens when you call `PriorityUp` for an item, and another `PriorityUp` on another item in next 15 minutes. I think your problem is ill-posed. What do you expect to happen with the priorities when you call `PriorityUp` with several items with different priorities? Perhaps reconsider your approach thinking about this, and when you'll be sure about what you want, please post some example input/output data. — BartoszKP, Sep 17 '13 at 15:21
If I have two items prA=3 and prB=2, must become PrA=2 and PrB=1. Increasing A and B sequently makes prA=3, prB=2 again — albert, Sep 17 '13 at 15:25

score 5 · Answer 1 · edited Sep 17 '13 at 15:16

5

Why not use an OrderedDictionary instead? Then the order within the dictionary can be your priority and you can just exchange items if you need to swap priorities. It does however mean if you add/remove/insert it will just handle the priority for you.

This way to increase your priority you can call RemoveAt(oldPriority) and Insert(newPriority).

edited Sep 17 '13 at 15:16

Andrew Morton

24,203
9
60
84

answered Sep 17 '13 at 15:10

Ian

33,605
26
118
198

What's the complexities of `Insert` and `RemoveAt`? The Microsoft docs doesn't seem to say. Is the underlying container just an array? – Bernhard Barker Sep 17 '13 at 15:38
Insert will have to be `newPriority - 1` since the item was first removed. – mao47 Sep 17 '13 at 15:41
@Dukeling: I was just stating that to change the priority of something, just change it's position in the OrderedDictionary and showing an easy way to do that. I'm not sure how it's implemented underneath is important. I'm assuming any calculation of priority will be correct (e.g. offsets from removed items). This is just to illustrate. – Ian Sep 17 '13 at 16:06
1

@Ian If it uses an array, `RemoveAt` and `Insert` would take O(n), which is not particularly efficient ([you can get O(log n)](http://stackoverflow.com/a/18854030/1711796)). So if it needs to be performant, how it's implemented underneath is absolutely important. – Bernhard Barker Sep 17 '13 at 16:15
@Dukeling: True, but the post only says that lookups need to be performant. Take a look at this post for a discussion on performance http://stackoverflow.com/questions/2565455/what-is-the-complexity-of-ordereddictionary – Ian Sep 17 '13 at 16:17

score 1 · Answer 2 · answered Sep 17 '13 at 15:33

Using a dictionary is not going to be particularly efficient. I recommend something like a (self-balancing) binary search tree (BST).

I say "something like" because we don't actually want to explicitly store the priorities, because otherwise we'll need to update many of them often.

Each node needs to have a count of it's children, so, when walking down the tree for an insert or delete, we know whether to go left or right based on the count of the nodes. After a delete, we can also walk back up the tree and update the counts.

As per a BST, insert and delete will take O(log n).

You will need to implement this data structure yourself, since it's a modified version of a BST, but implementing something like a red-black tree isn't too difficult.

Similarly, probably just about any modified sorted container will do.

You'll probably need this structure in addition to your current container, as you seem to require look-ups by string.

It's the more efficient solution, but it's quite a bit more effort.

OrderedDictionary performs these operations in O(n), so it's definitely more efficient there, however, the find for this will be O(log n), where OrderedDictionary is O(1), so it all depends on how often you use which operation. — Bernhard Barker, Sep 17 '13 at 16:59

score 0 · Accepted Answer · answered Sep 17 '13 at 15:41

Ok, referring to OP's comment I'm guessing that what they need is:

public void PriorityUp(Item it)
{
    if (DecreasePriority(it))
    {
        IncreaseOther(it.Priority, new[] { it });
    }
}

public void PriorityUp(IEnumerable<Item> items)
{
    List<int> toDecrease = new List<int>();
    foreach (var item in items)
    {
        if (DecreasePriority(item))
        {
            toDecrease.Add(item.Priority);
        }
    }

    foreach(var p in toDecrease)
    {
        IncreaseOther(p, items);
    }
}

private bool DecreasePriority(Item it)
{
    if(it.Priority <= 1)
    {
        return false;
    }

    it.Priority--;

    return true;
}

private void IncreaseOther(int priority, IEnumerable<Item> toIgnore)
{
    foreach (var item in allItems.Values.Except(toIgnore))
    {
        if (item.Priority == priority)
        {
            item.Value.Priority++;
        }
    }
}

However I have no idea what's all this for. Perhaps consider designs suggested in other answers.

Increasing several items at once is equivalent with sequential if we begin increasing from the item with the highest priority and so on. — albert, Sep 17 '13 at 18:12
This code will produce the expected result given input/output data you've provided in your comment. Please note the `toIgnore` collection, which solves the "priority flickering" problem. — BartoszKP, Sep 18 '13 at 10:59

Dictionary with priorities

3 Answers3