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

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

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

• siftUp 将太大的节点与其父节点交换（从而移动 ）直到它不大于它上面的节点。构建堆 函数获取未排序项目的数组并移动它们，直到它们 都满足堆性质。

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

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

siftUp-

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

加工-

从数组的开头应用 siftUp 操作。

筛选(4)-
没有交换，因为它是根

 heapified Array-a[4]

向上筛选(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]

筛选(6)-

首先在 (6,4) 之间交换，然后在 (6,5) 之间交换

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

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

筛选-

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

加工-

从数组末尾开始，我们将一一应用 siftDown 操作。

筛选(6)-

它没有孩子，所以没有交换。这同样适用于 siftDown(5) 和 siftDown(3) ，因为它们没有任何子级。所以它们不能进一步向下移动。

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

筛选(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 应用于同一组元素时，可能会有不同的堆。请澄清。 :)

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

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

第一种方法：

    6
   / \
  5   3
 / \
2   4

第二种方法：

    6
   / \
  5   3
 / \
4   2

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

    6
   / \
  4   5
 / \
2   3

但请注意，这两种方法虽然都能生成正确的结果，但它们具有不同的复杂性。看构建堆的时间复杂度怎么可能是O(n)？ https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity.