最大堆和插入

Question

我有一个大小为10的整数数组。我需要绘制完全二叉树，我已经做到了。现在我需要使用siftup过程插入另外三个元素。每次插入后都要展示最大堆。

我不确定"show the max heap following each insert"是什么意思。这是否意味着我需要在插入一个元素后展示最大堆的大小？

定义（最大堆）HEAP（X） 令X为一个全序集。堆是空的∅，或者它是一棵完全二叉树，t，由nt≥1个节点组成，每个节点都分配了X的值，使得： 节点i的值≤节点i的父节点的值，i = 2,3，...，nt。 堆的大小是树中节点的数量。如果堆的大小为0，则堆为空。

最大堆的定义如上所述，但对我来说似乎有点模糊。

- johnnily

---

最大堆的定义是这样的，但我觉得有点模糊不清。哪一部分让你感到模糊不清？你需要专注于这部分来提出问题。 - phant0m

Answer 1

你需要在每次插入后展示结果树。也就是说，如果最初你有一个堆。

   3
  / \
 1   2

当您插入一个5时，它将从最后的堆位置开始，并向上冒泡到堆头：

    3           5
   / \         / \
  1   2  =>   3   2
 /           /
5           1 

类似地，如果您插入了一个4，则会发生以下情况：

    5           5
   / \         / \
  3   2  =>   4   2
 / \         / \
1   4       1   3

- Juan Lopes

---

这个回答值得更多的投票，感谢出色的演示。 - M.kazem Akhgary

Answer 2

简单来说，最大堆是一个堆，其中父节点的值大于其任何子节点的值。当您绘制初始完全二叉树时，它已经是一个最大堆了吗？向上筛选（在我的学院中我们称之为冒泡，但是这不重要）有点难以在这样的线程上解释，因此我同意@DanteisnotaGeek的观点。维基百科文章有一个很好的图表，说明了如何进行向上筛选过程。要展示插入后的最大堆，需要绘制二叉树，使其满足每次插入后的最大堆属性。因此，最终您应该拥有初始树、第一次插入的树、第二次插入的树和第三次插入的树，总共4棵树。

- masotann

Answer 3

在堆中，任何时刻从根节点到叶子节点都是有序和线性的：

当您将元素插入堆的下一个插槽时，该行的顺序将更改： 因此，插入的最后一步变成了重新排序线性数据结构：冒泡排序。

- 宏杰李