algorithm - 通过依次插入以下元素创建一个堆

Question

问题:

Create a heap by inserting the following elements in the order that they are given. Show the heap after each insertion and trickle. (The heap should be implemented to keep the highest key value at the top.)

5 4 6 7 9 8 1 2 3

Once you have finished creating the heap, remove each element from it. Show the heap after each removal and trickle. Indicate which element has been removed in each step.

我知道如何将元素插入堆中，但如何创建它呢？而且我真的不确定如何从堆中删除元素。

Answer 1

我将假设一个二叉堆作为我的答案，有许多不同的堆，但由于这听起来像是家庭作业并且是一个相当基本的问题，我将涵盖最基本的堆:

好吧，首先堆是空的。

然后你插入 5，所以堆现在是:

5

然后在底部插入 4。 4 比 5 小，所以我们不改变它的父级位置。堆现在是:

   5
  /
 4

然后我们在底部插入 6，在 5 的下方(始终从左到右在底部插入)。我们将新插入的节点 (6) 的值与其父节点 (5) 的值进行比较，并意识到我们必须交换它们，以免违反堆属性:

   6
  / \
 4   5

现在我们在下一个可用位置(在 4 下方)插入 7，并将它与它的父元素交换，因为 7 > 4。然后我们再次交换(或滴入)，如 7 > 6 并得到:

    7
   / \
  6   5
 /
4

等等……