堆排序中用于堆化数组的siftUp和siftDown操作

Question

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

• siftDown会将一个太小的节点与其最大的子节点互换位置（从而将它向下移动），直到它至少与其下面的两个节点一样大。

• siftUp会将一个太大的节点与其父节点交换位置（从而将它向上移动），直到它不比上面的节点更大。buildHeap函数接受一个未排序的项目数组，并将它们移动，直到它们都满足堆属性。

---

对于buildHeap，可以采用两种方法之一。一种是从堆顶（数组开头）开始，对每个项目调用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)-上移节点(2)

由于父节点的值(4)更大，没有进行交换

heapified Array-a[4,2]

siftUp(3)-

父节点的值为4，不需要进行交换操作。

heapified Array-a[4,2,3]

-

其父节点的值为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,4,2]

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]

siftDown(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可能会得到不同的堆。请澄清一下。：）

- ViX28

---

你的例子证明了生成的堆可以不同。都对给定的元素有效。我能想到的另一个更小的例子是[1, 2, 3]。 - user612566

Answer 1

是的，可以为同一组元素拥有不同的堆。

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

第一种方法：

    6
   / \
  5   3
 / \
2   4

第二种方法：

    6
   / \
  5   3
 / \
4   2

事实上，如果您手动绘制它，还有其他可能的堆栈，例如：

    6
   / \
  4   5
 / \
2   3

请注意，尽管两种方法都能生成正确的结果，但它们具有不同的复杂性。请参见如何将堆构建为O(n)时间复杂度？。

- dejvuth

Answer 2

你描述的第一种方法（自顶向下）不是从未排序的数组构建堆的常规方法，这可能需要O(n log n)时间！这是因为它意味着必须在底部级别上执行sift-up操作（底部级别大小为n/2，其深度为log-n）。

正常的方法是对数组进行自下而上的扫描，并对每个节点执行sift-down。每个级别的时间将是该级别中节点数乘以高度（因为sift-down是递归的，可能会交换到底层）。总时间将是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

`

- gen-y-s