java - 最大/最小堆树可以包含重复值吗？

Question

我想知道是否允许最大或最小堆树具有重复值？我试图仅通过在线资源查找有关此信息的信息一直没有成功。

Answer 1

是的他们可以。您可以在“算法简介”（Charles E. Leiserson、Clifford Stein、Thomas H. Cormen 和 Ronald Rivest 撰写）中了解这一点。根据维基百科对二叉堆的定义：

根据为堆定义的比较谓词，所有节点的每个子节点要么[大于或​​等于]( max heaps )，要么[小于或等于]( min heaps )。

Answer 2

是的，他们可以有重复。从堆的维基百科定义：

要么父节点的key总是大于等于子节点 的key，最高的key在根节点（这种堆称为max heap），要么父节点的key 小于等于子节点的key子节点和最低键位于根节点（最小堆）

因此，如果它们具有相等的子节点，则意味着它们可以重复。

Answer 3

是的，但我会说不。为了提高效率，他们不应该有具有重复值的不同节点，否则它会失去它的目的（你必须搜索子节点等）。但是，您可以将每个节点设计为包含一个变量，该变量声明您在数据中拥有多少个该值的副本。

这又是我的看法。如果这是一种不好的做法，我希望有人能解释原因。我可能只需要做一些效率测试。如果您要存储简单的数据类型，例如 ints，那么我会发现它的效率较低，但对于具有 id 的较大对象节点来说，它似乎很好。