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

Question

我想知道是否允许最大或最小堆树具有重复值？我一直试图通过在线资源找到有关这方面的信息是不成功的.

Answer 1

是的他们可以.您可以在"算法导论"(Charles E. Leiserson,Clifford Stein,Thomas H. Cormen和Ronald Rivest)中了解这一点.根据维基百科中二进制堆的定义:

根据为堆定义的比较谓词,所有节点都是[大于或等于](最大堆)或[小于或等于](最小堆)其子节点.

他们也可以有。你只需要正确地实现你的遍历算法。在 BST 上，维基百科说它们不能有重复的值，但我刚刚提到的那本书允许这样做 - 只是稍微修改了遍历算法。底线 - BST 也可以拥有它们。 (2认同)

Answer 2

是的,他们可以有重复.来自维基百科对Heap的定义:

父节点的密钥总是大于或等于子节点的密钥, 最高密钥在根节点中(这种堆称为最大堆)或父节点的密钥小于或等于父节点的密钥 .子节点和最低键位于根节点(最小堆)

因此,如果他们有子节点相等的节点意味着他们可以重复.