java - 在最小堆中寻找最大值

Question

我正在为考试而学习，从我正在查看的一张工作表中，它要求为存储整数的最小堆编写一个 largest() 方法。

public class Heap {
   private int[] arr = new int[100];
   private int numElts = 0;

   public int largest(){

  }

}

最大大小为 100 个元素，newElt 跟踪堆中存储的当前元素数。

我正在考虑做类似的事情:

int[] newArr = Collections.sort(arr);
return newArr[newElt];

但是那会改变原来的堆。我可以对它进行深度复制，但它说没有必要检查堆的所有元素。

那么，有人可以建议一种无需查看每个元素的方法吗？谢谢，

Answer 1

如果您的结构是按堆顺序排列的，如果它是一个 -max 堆-，那么您的最大元素将只是 arr[0]。但是因为它是一个最小堆，所以你只知道最大元素是一个叶节点。

因此您不需要测试 - 每个 - 元素。但是您最多需要查看一半的元素(对于二叉树，叶子的数量在 1 到一半大小加一之间，包括两个帐户)。

您可以通过知道二叉堆(您所描述的)是一种特殊的平衡二叉树来快捷地查看叶节点，通过少量计算可以告诉您两组叶节点在哪里可能是。