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

Question

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

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];

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

那么任何人都可以提出一种方法来做到这一点，而无需查看每一个元素吗？谢谢，

score 3 · Accepted Answer

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

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

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

1 回答 1