Java 最大/最小堆树可以包含重复值吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22570126/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Can max/min heap trees contain duplicate values?
提问by Vimzy
I'm wondering if a max or min heap tree is allowed to have duplicate values? I've been unsuccessful in trying to find information regarding this with online resources alone.
我想知道是否允许最大或最小堆树具有重复值？我试图仅使用在线资源来查找有关此的信息，但一直没有成功。
采纳答案by ucsunil
Yes, they can. You can read about this in 'Introduction to Algorithms' (by Charles E. Leiserson, Clifford Stein, Thomas H. Cormen, and Ronald Rivest). According to the definition of binary heaps in Wikipedia:
是的他们可以。您可以在“算法简介”（Charles E. Leiserson、Clifford Stein、Thomas H. Cormen 和 Ronald Rivest 着）中阅读相关内容。根据维基百科中二元堆的定义：
All nodes are either [greater than or equal to](max heaps) or [less than or equal to](min heaps) each of its children, according to a comparison predicate defined for the heap.
根据为堆定义的比较谓词，所有节点都是 [大于或等于]( max heaps) 或 [小于或等于]( min heaps) 其每个子节点。
回答by zgc7009
Yes, but I would say no. For efficiency they shouldn't have different nodes with duplicate values or it loses it's purpose a bit (you would have to search child nodes and such). However, you could design each node to contain a variable that declares how many copies of that value you have in your data.
是的，但我会说不。为了效率，它们不应该有具有重复值的不同节点，否则它会失去它的用途（您必须搜索子节点等）。但是，您可以将每个节点设计为包含一个变量，该变量声明您的数据中有多少该值的副本。
Again this is my opinion. If this is a bad way of doing it I would love if someone could explain why. I might just have to do some efficiency testing. If you are storing simple data types like ints then I would see it being less efficient but for larger object nodes that have ids it's been nice, it seems.
这又是我的看法。如果这是一种糟糕的做法，我希望有人能解释原因。我可能只需要做一些效率测试。如果您要存储像 int 这样的简单数据类型，那么我会认为它效率较低，但对于具有 id 的较大对象节点来说，它似乎很好。
回答by Raul Guiu
Yes they can have duplicates.From wikipediadefinition of Heap:
是的，他们可以有重复。从维基百科对堆的定义：
Either the keys of parent nodes are always greater than or equalto those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equalto those of the children and the lowest key is in the root node (min heap)
无论是父节点的键始终大于或等于给那些孩子们的，最高的关键是根节点（这种堆被称为最大堆）或父节点的密钥是 小于或等于给那些子节点和最低键位于根节点（最小堆）中
So if they have children nodes that are equal means that they can have duplicated.
因此，如果它们的子节点相等，则意味着它们可以重复。
