4

我有一个项目类和一个项目字典。字典中的每个项目都有一个唯一的优先级（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）。

4

3 回答 3

5

为什么不使用OrderedDictionary呢？然后字典中的顺序可以是您的优先级，如果您需要交换优先级，您可以交换项目。但是，这确实意味着如果您添加/删除/插入，它只会为您处理优先级。

通过这种方式来提高您的优先级，您可以调用 RemoveAt(oldPriority) 和 Insert(newPriority)。

于 2013-09-17T15:10:58.417 回答
1

使用字典不会特别有效。我推荐类似（自平衡）二叉搜索树（BST）的东西。

我说“类似”是因为我们实际上并不想显式存储优先级，否则我们需要经常更新其中的许多。

每个节点都需要有一个count子节点，因此，当沿着树向下进行插入或删除时，我们可以根据count节点的数量知道是向左还是向右。删除后，我们还可以返回树并更新counts。

根据 BST，插入和删除将占用O(log n).

您需要自己实现这个数据结构，因为它是 BST 的修改版本，但实现像红黑树这样的东西并不难。

同样，可能几乎任何修改后的排序容器都可以。

除了当前容器之外，您可能还需要此结构，因为您似乎需要通过string.

这是更有效的解决方案，但需要付出更多的努力。

于 2013-09-17T15:33:40.677 回答
0

好的，参考 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++;
        }
    }
}

但是我不知道这一切是为了什么。也许考虑其他答案中建议的设计。

于 2013-09-17T15:41:38.890 回答