10
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ Note that linked lists are not great for cache locality. $\endgroup$
    – Criticizing Israel not allowed
    Commented Apr 28, 2022 at 17:18

1 Answer 1

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Thanks I was thinking of how to implement something like the ready queue for the OS, and that is what piqued my interest in a data structure like this. Also in a game I'm developing which behaves very much like an OS scheduling algorithm where it makes sense to limit the priority levels to a small number. I like the idea of a bit vector as that would minimize search time. Good to know this is used $\endgroup$
    – user4779
    Commented Apr 28, 2022 at 12:29
  • 2
    $\begingroup$ What's nice in the OS context is that when there's a high priority process ready to run, it's found on the first iteration of the loop, even without adding the bitmap of nonempty queues. In some applications, that's all that is needed. $\endgroup$
    – Mike Spivey
    Commented Apr 29, 2022 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.