algorithm - 堆 - 对未知输入执行 DeleteMax 操作 - 实现

Question

我需要你的帮助来找出/获得一种简单证明的方法。

假设给定一个具有 n 个不同元素的最大堆，x 是深度 D 中堆中的一个元素(在表示堆的树中)。现在假设我们正在执行一系列 DeleteMax 操作。

1. 从堆中提取 x 之前，需要执行 DeleteMax 操作的最大次数是多少。

2. 从堆中提取 x 之前需要执行的 DeleteMax 操作的最少数量是多少。

注意:

我相信我确实设法通过指定如果 x 和他的 parent 是堆中最大的元素然后 x 将在 D+1 DeleteMax 操作后提取(其中 D 专门用于提取他的 parent )来证明第二个).

我刚刚发现第一个方法不是很顺利，我不确定我需要使用什么方法来证明它是正确的。

Answer 1

我认为你是对的。第二种情况会发生，只有 x 的 parent 和祖 parent 大于 x，而不是堂兄弟、叔叔等……只有在根的一条直线上的前辈。

当只有 x 的 child 小于 x 时，会发生第一种情况。因此，如果堆的高度为 H，则最大值将为高度 H 的完整堆减去高度 H-D 的完整堆。