堆中的siftUp和siftDown操作，用于对数组进行堆化

Question

假设MAX-HEAPIFY操作。其中父元素值大于其子元素值。

>

siftUp将一个太大的节点与其父节点交换（从而将其向上移动），直到它不大于其上的节点。buildHeap函数获取一个未排序项的数组，并移动它们，直到它们都满足heap属性。

构建堆有两种方法。一种是从堆的顶部（数组的开始）开始，并对每个项调用siftUp。在每个步骤中，先前筛选的项（数组中当前项之前的项）形成一个有效的堆，向上筛选下一个项将其放入堆中的有效位置。筛选每个节点后，所有项都满足堆属性。第二种方法是相反的：从数组的末尾开始，向后移动到前面。在每次迭代中，您筛选一个项，直到它位于正确的位置。

让数组a有5个元素a[4,2,3,5,6]。

siftUp-

输入-a[4,2,3,5,6]

处理-

从数组开始应用siftUp操作。

siftUp（4）-
没有交换，因为它是根

 heapified Array-a[4]

siftUp（2）-

无交换作为父值（4）更重要

heapified Array-a[4,2]

（3）-

没有交换作为父值（4）是更多

heapified Array-a[4,2,3]

（5）-

它的父值是2，所以交换（5,2）。

          Array-a[4,5,3,2]

现在5的父值是4，所以再次交换（5,4）。

 heapified Array-a[5,4,3,2]

siftUp（6）-

先在（6,4）之间交换，然后在（6,5）之间交换

 heapified Array-a[6,5,3,2,4]

输出-a[6,5,3,2,4]

SiftDown-

输入-a[4,2,3,5,6]

处理-

从数组的末尾，我们将一个接一个地应用siftDown操作。

siftDown（6）-

它没有孩子，所以没有交换。siftDown（5）和siftDown（3）也是如此，因为他们没有孩子。所以他们不能再往下移动了。

到目前为止的数组-a[4,2,3,5,6]

siftDown（2）-

它与较大的子值交换。这里6是较大的一个。所以交换（2,6）。

现在数组将是-a[4,6,3,5,2]

下载（4）

4有两个孩子6和3。换大一点的。交换（4,6）完成。现在数组将是-a[6,4,3,5,2]

同样，4必须被交换，因为它有一个大于自身的子代，即5。所以交换（4,5）就完成了。

数组将是-a[6,5,3,4,2]

堆数组-a[6,5,3,4,2]

输出-a[6,5,3,4,2]

为什么在同一组元素上执行siftUp和siftDown操作时会得到两种不同的输出？或者，当siftUp和siftDown应用于同一组元素时，可能会有不同的堆。请澄清。：）

Answer 1

您描述的第一种方法（自上而下）不是从未排序数组构建堆的正常方法，可能是因为它需要O（n log n）时间！！这是因为它意味着必须在底层执行筛选操作（底层大小为n/2，其深度为log-n）。

通常的方法是对阵列进行自下而上的扫描，并对每个节点进行筛选。每个级别的时间将是级别中的节点数乘以高度（因为sift-down是reusrive，可能会一直交换到底部级别）。总时间为O（1*n/2*n/4 3*n/8...）=O（n）*（1/2 2/4 3/8 ...)=O（n）*2=O（n）。

`
1/2 + 2/4 + 3/8 + 4/16 + ... =

1/2 + 1/4 + 1/8 + 1/16 + ... +
    + 1/4 + 1/8 + 1/16 + ... +
          + 1/8 + 1/16 + ... +
                + 1/16 + ... +
                       + ... =

1 +
1/2 +
1/4 +
1/8 +
... = 2

`

Answer 2

是的，同一组元素可能有不同的堆。

两种方法都正确地生成满足堆属性的堆：父元素值大于其子元素值。

第一种做法：

    6
   / \
  5   3
 / \
2   4

第二种方法：

    6
   / \
  5   3
 / \
4   2

事实上，如果你用手画，还有其他可能的堆，例如。

    6
   / \
  4   5
 / \
2   3

然而，请注意，这两种方法虽然产生了正确的结果，但它们有不同的复杂性。看看构建堆的时间复杂度如何？。