堆中的siftUp和siftDown操作用于堆积阵列

Question

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

• siftDown交换节点是其最大的孩子太小（从而移动下来），直到它至少一样大，两个节点 下方。

• siftUp交换一个太大的节点与其父节点（从而移动它），直到它不大于它上面的节点。 buildHeap 函数获取一系列未排序的项目并移动它们，直到它们全部满足堆属性。

---

有一个可能采取buildHeap两种方法。一个是在堆顶部（数组的开头）开始 ，并在每个项目上调用siftUp 。在每一步中，先前筛选的项目（数组中当前项目的 之前的项目）形成一个有效的堆，然后筛选下一个 项，将其置于堆中的有效位置。在筛选出每个节点 之后，所有项都满足堆属性。第二种方法 的方向相反：从阵列的末端开始，向前移动 。在每次迭代中，您都会筛选一个项目，直到其位于正确的位置。

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

siftUp -

输入 - 从的开始处的[4,2,3,5,6]

处理 -

应用siftUp opearation阵列。

siftUp（4） -
没有交换作为其是根

heapified Array-a[4] 

siftUp（2） -

没有交换为亲值（4）更

heapified Array-a[4,2] 

siftUp（3） -

没有交换为亲值（4）更

heapified Array-a[4,2,3] 

siftUp（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] 

输出一个[6,5， 3,2,4]

siftDown-

输入 - 一个[4,2,3,5,6]

处理 -

从我们将施加siftDown操作逐个阵列的端部。

siftDown（6） -

它没有孩子所以没有掉。因为他们没有任何孩子，所以同样适用于siftDown（5）和siftDown（3）。因此他们不能进一步向下移动。

阵列至今 - 一个[4,2,3,5,6]

siftDown（2） -

它得到具有较大孩子值交换。这里6是较大的一个。所以交换（2,6）。

现在阵列时便会-a [4,6,3,5,2]

siftDown（4） -

4有两个子6和3交换与较大的一个。交换（4,6）完成。 现在阵列将是 - a [6,4,3,5,2]

再次4必须交换，因为它有一个比它自己更大的孩子，这是5。所以交换（4,5）完成。

阵列将是 - 一个[6,5,3,4,2]

Heapified阵列-a [6,5,3,4,2]

输出-A [6 ，5,3,4,2]

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

Answer 1

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

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

第一种方法：

6 
/\ 
    5 3 
/\ 
2 4 

第二种方法：

6 
/\ 
    5 3 
/\ 
4 2 

事实上，如果你手工绘制，还有其他可能的堆，例如

6 
/\ 
    4 5 
/\ 
2 3 

但是请注意，两种方法尽管生成正确的结果，但它们具有不同的复杂性。请参阅How can building a heap be O(n) time complexity?。

Answer 2

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

正常的方法是做一个自下而上阵列的扫描，并进行各节点的SIFT向下。每个级别的时间将是该级别中节点的数量乘以高度（因为筛选重新开始并可能一直切换到最低级别）。总时间为O（1 * n/2 + 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 

`