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 交换，依此类推，数组将以升序排序的值结束。

我不理解“绘制”最大堆的练习意味着什么，但我怀疑它是否意味着堆化数组，这就是你所做的。