在堆中多次使用相同的密钥

Question

在一堆（无论是最大堆还是最小堆）中，是否可能存在两次或多次相同的密钥？

这种情况如何破坏O(n)的时间复杂度makeheap()和O(log(n))插入和删除？

例如： 以下堆有效吗？

1 

/\ 

1 1 

Answer 1

有时候理论扰动参数是很好回答这类的问题。想象一下堆中的每一个元素，当元素被插入到堆中时，您还会存储一个到目前为止已经完成的操作数量的“索引”，无论是构建或访问堆栈中的任何内容。因此，堆中的每个元素都有一个次要唯一标识，当堆中的两个值相等时，您可以使用它来打破“连接”，并且您仍然需要对它们进行比较。那么显然这个堆将像往常一样运行，并且具有相同的运行时间保证。找出这样的扰动是围绕这些退化问题的简单方法，特别是在计算几何问题时，如果你不想要一个线上的3个点，或者一个圆上有4个点等等。

但是，我给了你对你的问题有点迂回的回答。我相信真正的事实是，在堆操作中，只要被交换的子元素小于或等于它的父元素，就可以随意决定哪些元素与父元素进行交换（假设min-堆），并且一切都应该正常工作。唯一可能让事情变得更加复杂的是，如果出于某种原因，您想要立即将所有关系以最小值排除在堆外。但我相信，即使这并不是什么大不了的事情。

Answer 2

是否有可能有相同的密钥两次或多次？

是的，这是可能的。

这种情况如何破坏时间复杂性？

它不能。看看你选择的堆实现。为了导出O-符号，证明复杂性的上限是简单而直接的，而不对所涉及的值作任何假设。这意味着，例如，值可以重复，而不会影响复杂性。