Why do priority queues mostly use 0 as the most important priority?

Question

Why are most priority/heap queues implemented as 0 being the highest priority? I'm assuming I'm missing out some key mathematical principle. As I was implementing my own priority queue recently it seemed easier to write the insert function if priority went up with the integer value, but apparently people smarter than me think it should go the other way.

Any ideas?

Answer 1

Most priority queues are implemented as a fibonacci heap or something similar. That data structure supports extracting the minimum in constant time, which makes it natural to make 0 the highest priority, and take elements out of the queue by extracting the minimum.

Answer 2

I don't think there's any design reason for it. It's probably just because most programmers are used to thinking of 0 as the first element. Another reason might be because enumerators start at 0 so the first defined enum "Highest" integer value will be 0.

Answer 3

If it's ever increasing, how could you ever set anything to the highest priority? (+1 for rossfab's answer :)

Answer 4

As a counterexample, in what's surely one of the most readily available (if not used) priority queue implementations, namely STL's std::priority_queue, the top() element is the one numerically highest according to operator<. Of course everyone is used to the convention of lowest in sort order being front of queue so this catches a lot of people out the first time they use it.

Answer 5

The reason it's often the other way is that priority queues are used to implement algorithms like Dijkstra's and A*, where the priority is the distance to the node, and you want to process closer nodes first.

Answer 6

There is nothing inherent about a priority queue that makes 0 a better choice for top priority. For someone writing a reusable implementation however, you will have to pick something, and 0 is well defined no matter what type of integral or floating point value you use for your priority.

Even in writing a private implementation, if you decide you only need 256 priority levels and use an unsigned char as your priority and have 255 be your top priority, then you will need to carefully look over all your code if you decide that you need more levels.