最大/最小堆树是否包含重复值？

java binary-tree heapsort min-heap max-heap

2022-09-01 07:39:46

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

答案 1

是的，他们可以。你可以在“算法导论”（Charles E. Leiserson，Clifford Stein，Thomas H. Cormen和Ronald Rivest）中读到这一点。根据维基百科中二进制堆的定义：

根据为堆定义的比较谓词，所有节点要么[大于或等于]（最大堆数）要么[小于或等于]（最小堆数）每个子节点。

答案 2

是的，他们可以有重复项。来自维基百科对堆的定义：

父节点的键始终大于或等于子节点的键，并且最高键位于根节点中（这种堆称为最大堆），或者父节点的键小于或等于子节点的键，并且最低键位于根节点中（最小堆）

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