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

Question

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

• siftDown swaps a node that is too small with its largest child (thereby moving it down) until it is at least as large as both nodes below it.

• siftUp swaps a node that is too large with its parent (thereby moving it up) until it is no larger than the node above it. The buildHeap function takes an array of unsorted items and moves them until it they all satisfy the heap property.

---

There are two approaches one might take for buildHeap. One is to start at the top of the heap (the beginning of the array) and call siftUp on each item. At each step, the previously sifted items (the items before the current item in the array) form a valid heap, and sifting the next item up places it into a valid position in the heap. After sifting up each node, all items satisfy the heap property. The second approach goes in the opposite direction: start at the end of the array and move backwards towards the front. At each iteration, you sift an item down until it is in the correct location.

令数组 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]

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]

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

siftDown-

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

处理-

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

筛选(6)-

它没有 child 所以没有交换。这同样适用于 siftDown(5) 和 siftDown(3)，因为他们没有任何 child 。所以他们不能再往下移动。

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

筛选(2)-

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

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

筛选(4)-

4 有两个 child 6 和 3。与较大的 child 交换。交换 (4,6) 完成。现在 Array 将是 - a[6,4,3,5,2]

同样 4 必须被交换，因为它有一个比它自己大的 child ，也就是 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

其实如果你手画的话，还有其他可能的堆，e.g.

    6
   / \
  4   5
 / \
2   3

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