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

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





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

筛选-

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

加工-

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

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

 heapified Array-a[4]

siftUp(2)-

没有交换，因为父值(4)更多

heapified Array-a[4,2]

siftUp(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操作。

siftDown(6)-

它没有 child ，所以没有交换。 siftDown(5)和siftDown(3)也没有 child ，因此无法向下移动。

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

siftDown(2)-

它被替换为较大的子值。这里6是较大的一个。因此交换(2,6)。

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

siftDown(4)-

4有两个 child 6和3。与较大的 child 交换。交换(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应用于同一组元素时，可能具有不同的堆。请说清楚。 :)

最佳答案

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

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

第一种方法:

    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?。

关于arrays - 堆中的siftUp和siftDown操作用于堆放数组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34329942/