Would it make sense to use an array of linked lists for a Priority Queue, given a fixed number of priorities?

From what I can gather priority queues are typically implemented with heaps. If I have a small fixed number of priorities (such as 4), wouldn't a small array where each index represents the priority, and indexes into the associated linked list at that priority, be a more efficient implementation than using a heap, allowing O(1) time for all operations? Searching for the next element would be O(1) as only 4 indexes need scanning (beginning at index 0) to find a linked list that isn't empty.

I haven't seen this mentioned anywhere or in my course so am just curious if there's a reason this isn't done.

Not only does it make sense, it's a common data structure in operating systems to implement the ready queue for tasks. Operating systems typically have a fixed number of priority levels, so it makes sense.

One optimisation if you have a lot of priority levels (say, 64 to 256 of them) is to also maintain a bit vector to represent which priorities have items in them. You can then use word operations (e.g. find first set) to find the highest-priority element.

StackExchange Computer Science Q#151073, answer score: 16