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

siftUp and siftDown operation in heap for heapifying an array

假设MAX-HEAPIFY操作。其中 parent 元素值大于其 child 值。

  • 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 操作。

siftUp(4)-
没有交换,因为它是根

 heapified Array-a[4]

siftUp(2)-

没有交换,因为 parent 值 (4) 更多

heapified Array-a[4,2]

siftUp(3)-

没有交换,因为 parent 值 (4) 更多

heapified Array-a[4,2,3]

siftUp(5)-

它的parent值为2所以交换(5,2)。

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

现在 5 的 parent 值为 4,所以再次交换 (5,4)。

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

siftUp(6)-

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

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

output-a[6,5,3,2,4]

siftDown-

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

处理中-

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

筛选(6)-

它没有 child 所以没有交换。这同样适用于 siftDown(5) 和 siftDown(3),因为它们没有任何 child.So 它们无法进一步向下移动。

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

筛选(2)-

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

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

筛选(4)-

4 有两个 child 6 和 3。与较大的交换。交换 (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]

Output-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

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

您描述的第一种方法(自上而下)不是从未排序数组构建堆的正常方法,可能是因为它需要 O(n log n) 时间!!这是因为它意味着必须在底层执行筛选操作(底层大小为 n/2,深度为 log-n)。

通常的做法是对数组进行自下而上的扫描,然后对每个节点进行筛选。每个级别的时间将是级别中的节点数乘以高度(因为筛选是递归的,并且可能一直交换到底部级别)。总时间为 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

`