Priority Dictionary

Question

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

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 a dictionary to find an item effectively. Increasing the priority of some elements should lead to some change in the priorities of other people.

To be more clear: I have a collection of N elements (list, array, dictionary ...) I chose the dictionary because I have to perform some other operations. Each element has a field priority with some unique value 1 <= P <= N.

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

Answer 1

Good, citing OP comment. I guess they need:

 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 all this is for. Perhaps consider projects suggested in other answers.

Answer 2

Why not use an OrderedDictionary instead? Then ordering in the dictionary can be your priority, and you can simply swap items if you need to change priorities. However, this means that if you add / remove / insert, it will simply handle the priority for you.

Thus, to increase your priority, you can call RemoveAt (oldPriority) and Insert (newPriority).

Answer 3

Using a dictionary will not be particularly effective. I recommend something like (self-balancing) a binary search tree (BST).

I say "something like" because we actually do not want to explicitly store priorities, because otherwise we need to update many of them often.

Each node must have a count its children, so when passing through a tree by insertion or deletion, we know whether to go left or right based on count nodes. After removal, we can also back up the tree and update count s.

According to BST, inserting and deleting will take O(log n) .

You will need to implement this data structure yourself, as this is a modified version of BST, but implementing something like a red-black tree is not too difficult.

Likewise, perhaps something like any modified sorted container.

You will probably need this structure in addition to your current container, as it seems to you that you need to view with string .

This is a more effective solution, but it is a bit more effort.