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

Question

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

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

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

---

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

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

筛选-

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

加工-

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

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

Answer 1

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

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

第一种方法：

    6
   / \
  5   3
 / \
2   4

第二种方法：

    6
   / \
  5   3
 / \
4   2

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

    6
   / \
  4   5
 / \
2   3

但请注意，这两种方法虽然都能生成正确的结果，但它们具有不同的复杂性。请参阅构建堆的时间复杂度如何达到 O(n)？。