Chapter 6 - Heapify

Max-heap property

The max-heap property:

for every node i other than the root     A[ Parent( i ) ] ≥ A[ i ]

Note that the root is excluded as it has no parents.

In English, the max-heap property means that the parent value ≥ child value

Max-Heapify

Max-Heapify function, given a tree that is a heap except for node i, arranges node i and it's subtrees to satisfy the heap property.

Max-Heapify maintains max-heap property on an array as data is updated.

Helper function definitions used by Max-Heapify

Parent( i ) return ⌊i/2⌋ Left( i ) return 2i Right( i ) return 2i + 1

For simplicity, we assume an array size large enough for a full binary tree with empty leaves filled with -∞.

 

Pre and post conditions of Max-Heapify in ESCJava

Max-Heapify (A, i) //@ pre   A != null && i >= 1 && i < A.length &&               (\forall int j;                    j > i && j <= A.length/2;                    A[ j ] >= A[ left( j ) ] && A[ j ] >= A[ right( j ) ]); //@ post (\forall int j;                   j >= \old( i ) && j <= A.length/2;                  A[ j ] >= A[ left( j ) ] && A[ j ] >= A[ right( j ) ]);

Precondition says that the all subtrees of i are max heaps

Postcondition says that the i subtree is a max heap.

Note that leaves are in array indices greater than A.length/2.

Running Heapify

MAX-HEAPIFY operation:

Find location of largest value of:

A[ i ], A[ Left( i )] and A[ Right( i ) ]

If not A[ i ], max-heap property does not hold.

Exchange A[ i ] with the larger of the two children to preserve max-heap property.

Continue this process of compare/exchange down the heap until subtree rooted at i is a max-heap.

At a leaf, the subtree rooted at the leaf is trivially a max-heap.

Max-Heapify (A, 2)

1 2 3 4 5 6 7 8 9 10 16 4 10 14 7 9 3 2 8 1 1 2 3 4 5 6 7 8 9 10 16 14 10 4 7 9 3 2 8 1 Exchange i with largest child

1 2 3 4 5 6 7 8 9 10 16 14 10 8 7 9 3 2 4 1 Exchange i with largest child Example: Max-Heapify( A, 2 ) (a) Node 2 violates the max-heap property. for every node k other than the root        A[ Parent( k ) ] ≥ A[ k ] (b) Compare node 2 with its children, and then exchange with the larger of the two children. (c) Continue down the tree, exchanging until the value is properly placed at the root of a subtree that is a max-heap; in this case, at a leaf.

Analysis of Heapify Running Time

The standard Divide-and-Conquer algorithm usually works as follows:

1. spend some time handling the base case
   
2. if not at the base case, divide the problem up into smaller subproblems: D(n)
   
3. make recursive calls to handle all the subproblems created on step 2: T(n/b)
   
4. combine results created by recursive calls on step 3: C(n)
   

Max-Heapify is a degenerate (meaning not standard) version of a Divide-and-Conquer algorithm

• Multiple base cases, appearing in line 3, 6 and 8, constant time for any base case is Θ(1):
  
  • 3     if l > A.heap-size
                   and
  • 6     if r > A.heap-size 

    then Max-Heapify has reached the base case, i.e., Max-Heapify has reached a node in the tree with empty left and right subtrees.

  • 8     if largest = i

    then Max-Heapify has reached the base case, i.e., Max-Heapify has reached a node in the tree with empty left and right subtrees or the parent is larger than either child.

• There is no combining part to this algorithm, i.e., no work is done after the recursive call returns since solution occurs in place.

• Applying recurrence analysis:
  
  • T(n) = a * T(n/b) + f(n)
    
    • a = number of subproblems
    • n/b = size of the subproblems
    • f(n) = D(n) + C(n)
      
  • For Max-Heapify
    
    • a = 1, i.e., there is only one recursive call made
      
    • n/b = (2/3) * n, is the worst case size of the one subproblem
      
      • The worst case is when the last level of the tree is half full.
        
      • That's when the left subtree has one entire full level as compared to the right subtree.
        
      • In this worst case, Max-Heapify has to "float down" through this left subtree.
        
      • The size of the left subtree is (2/3) * n, see table for numeric analysis.
        
    • f(n) = Θ(1), all the work done in lines 1 - 9 above takes a constant time
      
    • T(n) = T(2n/3) + Θ(1)
      
  • Applying Master Method
    
    • a = 1, b = 3/2, f(n) = 1 and n^log_b^a =  n^log_3/2¹ = n⁰ = 1
      
    • Case 2 applies since f(n) =  Θ(n^log_b^a) = Θ(1)
      
    • T(n) = Θ(lg n)
      
  • Since the height h = ⌊lg n⌋, we can also say that Max-Heapify is Θ(h)

Question 6.4 - Give an algorithm to determine if an array is a heap.

What is the recurrence equation?

Determine the run time?

Does this make sense?