Is this a reasonably performant way to implement priority queues?

Unity Engine
1

I have some container OverrideContent that contains an int indicating its priority, and whatever other data I want to store in it. I’m trying to figure out the most performant way to pass in an int representing a unique NPC identifier, and get back the instance of OverrideContent which contains the highest priority. The most straightforward possible way of accomplishing this is something like the following:

[System.Serializable]
public class OverrideContent
{
    public int priority;
    //Data we want to use
}

List<OverrideContent> overrideList;

public GetHighestPriority()
{
    float highestPriority = -1;
    OverrideContent bestContent = null;

    for (int i = 0; i < overrideList.Count; i++)
    {
        if (overrideList[i].priority > highestPriority)
        {
            bestContent = overrideList[i];
            highestPriority = bestContent.priority;
        }
    }

    return bestContent;
}

This is clean, but it’s very primitive; I’m just storing a huge list of potential overrides for every ID, and iterating through them every time someone accesses the ID. It works, but it’s slow. Is there an obvious, superior way to structure this that I’m missing, or are the lists likely to be perfomant enough that any more tinkering would step into the land of premature optimization?

2

Even something specific like that can depend on your use-case, unless you’re looking for a single but very generic/flexible version. Generalization often comes with drawbacks in regards to performance - which is often still acceptable unless you’re doing low-level programming or creating realtime application where every bit of performance matters.

If you want to optimize lookups and keep it as simple as possible, the first question that comes to my mind is about the ratio of adding items to the list and the number of look-ups. If look-ups happen quite often/frequently and inserting items does only happen once in a while, you’d surely be better off using a sorted list so that you can just grab the very first item once you request the highest priority.

If both happen a lot or you want one single solution for the problem, you’re either gonna make some compromises or do some more research regarding this topic.
In any case, I’d probably have an interface or a base class that can be used to implement different versions, not only for the ease of different tests but it might also be useful for different use cases (i.e. different requirements / circumstances).

3

I’m definitely performing lookups much more frequently than I am inserting/sorting/removing data, so the sorted list seems reasonably simple, especially since the actual sort operation would only have to occur when the list was modified, compared to every time something was retrieved; thank you for the suggestion!

4

Ye, than this is defintely the first step into the right direction, at least in this particular situation.
I’d still build an abstraction layer for that, even though this might be an application-specific requirement for you at the moment.

5

That’s a great suggestion as well- these days I’ve been trying to keep as much public functionality as possible abstracted ^^

6

The classes you need to run your test already exist.
System.Collections.Generic.List<KeyValuePair<TKey, TValue>>
System.Collections.Generic.SortedList<TKey, TValue>

Both implement the interface System.Collections.Generic.ICollection<KeyValuePair<TKey, TValue>>
Simply make your code work against an ICollection<KeyValuePair<TKey, TValue>> and try out the performance of List vs SortedList.