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

Question

我需要你的帮助，试图找出/获得一个简单证明的方法。

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

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

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

笔记：

我相信我确实设法证明了第二个，即如果 x 和他的父母是堆中最大的元素，那么 x 将在 D+1 DeleteMax 操作之后被提取（其中 D 个专门用于提取他的父母）。

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

Answer 1

我想你是对的。当只有 x 的父母和祖父母大于 x 时，会发生第二种情况，而不是堂兄弟、叔叔等……只有与根成一直线的前辈。

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