建立堆程序。 [英] Build Heap Procedure.

问题描述

大小为n的整数数组可以通过调整从完整的二叉树的每个内部节点处生根的堆（从节点⌊（n-1）/2⌋开始）并执行此调整直到根节点（根节点在索引0处）的顺序为⌊（n-1）/ 2，⌊（n-3）/2⌋，.....，0。

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n−1)/2⌋ and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n−1)/2, ⌊(n−3)/2⌋, ....., 0.

============================================== ============================

==========================================================================

我知道，这是一个内部版本堆过程需要O（n）时间，但是有人可以通过取一个n较小的数组来显示事物的工作方式来使我形象化吗？

I know, it's a Build Heap procedure and takes O(n) time, but can someone please make me visualise by taking a array with small value of n to show how things are working?

推荐答案

我们以数组 [7，3，9，1，2，4，8，8，5，6，0] 为例。树结构为：

Let's do an example with the array [7, 3, 9, 1, 2, 4, 8, 5, 6, 0]. The tree structure is:

         7
    3         9
  1   2     4   8
 5 6 0

堆中有10个项目。因此，从索引（n / 2）-1（第一个非叶子节点）开始，我们看到值2大于其一个子节点。我们交换，得到：

There are 10 items in the heap. So, starting at index (n/2)-1 (the first non-leaf node), we see that the value 2 is greater than its one child. We swap, giving:

         7
    3         9
  1   0     4   8
 5 6 2

接下来，1小于其子级，所以我们不理会它。

Next, 1 is smaller than its children, so we leave it alone.

9大于两个孩子。规则是您将其交换给最小的孩子，得到：

9 is larger than both of its children. The rule is that you swap it with its smallest child, giving:

         7
     3       4
   1   0   9   8
  5 6 2

3大于两个孩子，因此交换它的值为0。它也大于2，因此我们进行了另一个交换。结果是：

3 is larger than both of its children, so swap it with 0. It's also larger than 2, so we do another swap. The result is:

         7
     0       4
   1   2   9   8
  5 6 3

最后，7大于0，因此我们将其交换，将0置于根。 7也大于其两个子级，因此我们将其交换为1。7大于5和6，因此将其交换为叶级。结果是：

Finally, 7 is larger than 0, so we swap it, placing 0 at the root. 7 is also larger than its two children, so we swap it with 1. And 7 is larger than 5 and 6, so we swap it to the leaf level. The result is:

         0
     1       4
   5   2   9   8
  7 6 3

这是有效的最小堆。

这篇关于建立堆程序。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！