java - 数组的最大堆表示

Question

作为一个家庭作业问题，我必须从数组中取出最大堆。问题如下:

请取出以下数组中存储的最大堆(堆大小为6)A[] = {15,10,8,5,2,7,20,30}

所以，当我尝试这个问题时，我只是用老式的方式来做，没有考虑到 heapSize 小于数组大小。

我得到的最大堆是:{30,20,15,10,2,7,8,5}

我的问题是:这是正确的吗？另外，现在 heapSize 小于数组大小，这对生成的最大堆有何影响？我应该只显示最大堆数组直到第 6 个元素还是应该修改我的最大堆？

谢谢!

Answer 1

我认为你误解了这个练习。

如果我们按照字面意思进行练习，并从给定数组中“抽出”大小为 6 的最大堆，我们将得到一棵如下所示的树:

      15
   10    8
  5  2  7 20
30

您可以看到数组的前 6 个元素是按堆顺序排列的。

这看起来也很像堆排序的中间状态:最大值 30 是最后一个元素，其次是第二大的 20。如果我们遵循堆排序算法，将当前最大堆元素 15 与最后一个元素 7 交换，等等，该数组最终将以升序排列的值。

我不明白“抽出”最大堆的练习是什么意思，但我怀疑这意味着堆化数组，这就是你所做的。