Словарь с приоритетами

У меня есть элемент класса и словарь элементов. Каждый элемент в словаре имеет уникальный приоритет (от 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

Я хочу найти полученный приоритет (от 1 до N) всех элементов, когда я выбираю некоторые и увеличиваю/уменьшаю P.

3 4
c# algorithm

3 ответа:

Хорошо, ссылаясь на комментарий опа, я предполагаю, что им нужно: 

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++;
        }
    }
}
Однако я понятия не имею, для чего все это. Возможно, рассмотрим конструкции, предложенные в других ответах.
0

Почему бы вместо этого не использовать OrderedDictionary? Тогда порядок внутри словаря может быть вашим приоритетом, и вы можете просто обмениваться элементами, если вам нужно поменять приоритеты. Однако это означает, что если вы добавляете / удаляете / вставляете, он будет просто обрабатывать приоритет для вас.

Таким образом, чтобы увеличить свой приоритет, вы можете вызвать RemoveAt(oldPriority) и Insert (newPriority).

5

Использование словаря не будет особенно эффективным. Я рекомендую что-то вроде (самобалансирующегося) бинарного дерева поиска (BST).

Я говорю "что-то вроде", потому что на самом деле мы не хотим явно хранить приоритеты, потому что в противном случае нам придется часто обновлять многие из них. Каждый узел должен иметь count своих потомков, поэтому, когда мы идем вниз по дереву для вставки или удаления, мы знаем, идти ли влево или вправо на основе count узлов. После удаления мы также можем вернуться вверх по дереву и обновить counts.

В соответствии с BST, вставка и удаление будут принимать O(log n).

Вам нужно будет реализовать эту структуру данных самостоятельно, так как это модифицированная версия BST, но реализовать что-то вроде красно-черного дерева не слишком сложно.

Точно так же, вероятно, подойдет любой модифицированный сортированный контейнер.

Вам, вероятно, понадобится эта структура в дополнение к вашему текущему контейнеру, поскольку вы кажется, требуется поиск по string.

Это более эффективное решение, но оно требует гораздо больше усилий.
1