具有优先级的字典
本文关键字:字典 优先级 | 更新日期: 2023-09-27 18:31:43
>我有一个类项目和一个项目字典。字典中的每个项目都有一个唯一的优先级(1 到 N)。当我从字典中删除项目时,所有其他优先级都会更新。我想在字典中实现一些增加/减少优先级。如果我想增加单个项目的优先级,我会将优先级与下一个较低的项目交换。问题是增加项目集合的优先级
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
}
我有字典,以便有效地找到一个项目。提高某些项目的优先级必然会对其他项目的优先级产生一些变化
更清楚的是:我有一个 N 个项目的集合(列表、数组、字典......我选择了字典,因为我还必须执行其他一些操作。每个项目都有一个字段优先级,其中包含一些唯一值 1<=P<=N。
我想在选择一些并增加/减少 P 时找到所有项目的结果优先级(1 到 N)。
为什么不使用 OrderedDictionary 呢?然后,字典中的顺序可以是您的优先级,如果您需要交换优先级,您可以交换项目。但是,这确实意味着如果您添加/删除/插入,它将只为您处理优先级。
通过这种方式,您可以调用RemoveAt(oldPriority)和Insert(newPriority)。
使用字典不会特别有效。我推荐类似(自我平衡)二叉搜索树(BST)的东西。
我说"类似"是因为我们实际上不想显式存储优先级,否则我们需要经常更新其中的许多优先级。
每个节点都需要有一个子节点的count
,因此,当沿着树向下移动以进行插入或删除时,我们根据节点的count
知道是向左还是向右移动。删除后,我们还可以回到树上并更新count
。
根据BST,插入和删除将需要O(log n)
。
您需要自己实现此数据结构,因为它是BST的修改版本,但是实现红黑树之类的东西并不太困难。
同样,可能几乎任何修改过的排序容器都可以。
除了当前的容器之外,您可能还需要此结构,因为您似乎需要按 string
进行查找。
这是更有效的解决方案,但要付出更多的努力。
好的,参考OP的评论,我猜他们需要的是:
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++;
}
}
}
但是我不知道这一切是为了什么。也许可以考虑其他答案中建议的设计。