c++ - 为什么优先级队列大多使用 0 作为最重要的优先级？

Question

为什么大多数优先级/堆队列实现为 0 是最高优先级？我假设我错过了一些关键的数学原理。当我最近实现自己的优先级队列时，如果优先级随整数值上升，编写插入函数似乎更容易，但显然比我聪明的人认为它应该采用另一种方式。

有任何想法吗？

Answer 1

大多数优先级队列都实现为斐波那契堆或类似的东西。该数据结构支持在恒定时间内提取最小值，这使得将 0 设为最高优先级并通过提取最小值将元素从队列中取出是很自然的。

Answer 2

如果它一直在增加，你怎么能将任何东西设置为最高优先级？（+1 为 rossfab 的回答 :)

Answer 3

通常是另一种方式的原因是优先级队列用于实现像 Dijkstra 和 A* 这样的算法，其中优先级是到节点的距离，并且您希望首先处理更近的节点。

Answer 4

我认为没有任何设计原因。这可能只是因为大多数程序员习惯于将 0 视为第一个元素。另一个原因可能是因为枚举数从 0 开始，所以第一个定义的枚举“最高”整数值将是 0。

Answer 5

作为一个反例，在最容易获得（如果不使用）的优先级队列实现之一，即 STL 中，std::priority_queue元素top()是根据. 当然，每个人都习惯了最低排序顺序排在队列前面的约定，所以这会在他们第一次使用它时吸引很多人。operator<

Answer 6

优先级队列本身并没有使 0 成为最高优先级的更好选择。然而，对于编写可重用实现的人来说，您必须选择一些东西，并且无论您使用哪种类型的整数或浮点值作为优先级，0 都是明确定义的。

即使在编写私有实现时，如果您决定只需要 256 个优先级并使用 unsigned char 作为您的优先级并将 255 作为您的最高优先级，那么如果您决定需要更多，则需要仔细查看所有代码水平。