siftUp and siftDown operation in heap for heapifying an array

Question

Assume MAX-HEAPIFY operation. where the parent element value is greater than its child values.

• 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.

Let the array a has 5 elements a[4,2,3,5,6] .

siftUp-

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

processing-

Applying siftUp opearation from the beginning of the array.

siftUp(4)-
no swap as its is the root

 heapified Array-a[4]

siftUp(2)-

no swap as parent value(4) is more

heapified Array-a[4,2]

siftUp(3)-

no swap as parent value(4) is more

heapified Array-a[4,2,3]

siftUp(5)-

its parent value is 2 so swap (5,2).

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

now 5's parent value is 4 so again swap (5,4).

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

siftUp(6)-

first swap between (6,4) then between (6,5)

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

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

siftDown-

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

Processing-

From end of the array we will be applying siftDown operation one by one.

siftDown(6)-

It has no child so no swap. The same applied for siftDown(5) and siftDown(3) also as they dont have any child.So they cant move further down.

Array till now - a[4,2,3,5,6]

siftDown(2)-

It gets swapped with the larger child value. Here 6 is the larger one. so swap (2,6).

Now Array wil be -a[4,6,3,5,2]

siftDown(4)-

4 has two child 6 and 3. swap with the larger one. swap (4,6) done. Now Array will be- a[6,4,3,5,2]

Again 4 has to be swapped because it has a child which is greater than itself, which is 5 . so swap (4,5) is done.

Array will be - a[6,5,3,4,2]

Heapified array -a[6,5,3,4,2]

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

why am I getting two different outputs when doing siftUp and siftDown operation on same set of elements? Or it is possible to have different heaps when siftUp and siftDown applied to the same set of elements. Please clarify. :)

Solution 1

Yes, it's possible to have different heaps for the same set of elements.

Both approaches correctly produce heaps satisfying the heap property: the parent element value is greater than its child values.

The first approach:

    6
   / \
  5   3
 / \
2   4

The second approach:

    6
   / \
  5   3
 / \
4   2

In fact, if you draw it by hand, there are other possible heaps, e.g.

    6
   / \
  4   5
 / \
2   3

Note however that both approaches, although generate correct results, they have different complexities. See How can building a heap be O(n) time complexity?.

Solution 2

The first approach you describe (top-down) is not the normal approach to building a heap from a unsorted array, probably because it would take O(n log n) time !! This is because it implies having to perform sift-up operations on the bottom levels (bottom level size is n/2 and its depth is log-n).

The normal approach is to do a bottom up scan of the array, and perform a sift-down of each node. The time for each level would be the number of nodes in the level multiplied by the height (since sift-down is recusrive and might swap all the way to the bottom level). The total time would be 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

`