Chapter 6 - Build Heap

Build-Max-Heap

• "Max" refers to the fact that this algorithm calls Max-Heapify, which guarantees that the object the with the largest value at the top of the heap.
• If Max-Heapify accepted a comparison operator instead of hardwiring the > operator, then this would implement Build-Heap.

Example - Building a max-heap from the following unsorted array results in the first heap example.

A.length = 10

i starts at 5, the last parent in the array: always at  ⌊ n/2 ⌋

Max-Heapify is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.

Note that Max-Heapify is run on each node that is a parent:

starts with the last parent in the array: always at  ⌊n/2⌋

Proof of Correctness:

• Loop Invariant - At the start of each iteration of the for loop, each node located at i + 1, i + 2, ..., n, is the root of a max heap.

  //@  forall int j;     i < j ≤ A.length;     A[ j ] ≥ A[Left( j )] && A[ j ] ≥ A[Right( j )]             for i ← ⌊A.length/2⌋ downto 1 do Max-Heapify ( A, i )

• Initialization
  • Prior to the first trip through the loop, i = ⌊n/2⌋ the last parent node.
    • Note that the left and right subtrees of the tree located at i=⌊n/2⌋ are leaves and trivially satisfy the heap property. 
      
  • The i ← ⌊A.length/2⌋ initialization in the for statement makes i < j ≤ A.length all the leaf nodes.
    
  • All nodes in locations i +1, i + 2, ..., n, are leaf nodes which is the trivial case for having the heap property.
    
• Maintenance: 
  • Each time through the loop, Max-Heapify (A, i) is called.  
    
  • The precondition for Max-Heapify states that the left and right subtrees of the tree located at i must satisfy the heap property. 
    • By the loop invariant,  the left and right subtrees of i satisfy the heap property.
      
  • The postcondition of Max-Heapify states that the tree rooted at location i satisfies the heap property.
    
  • After decrementing i at the end of the for loop, the loop invariant is reestablished.
    
• Termination:
  • At termination, i = 0. 
    • The tree rooted at location 1 satisfies the heap property, because i = 0, i < j ≤ A.length and the loop invariant still holds for the entire tree.
      
    • The loop invariant satisfies the Build-Heap post condition.
      

    //@  forall int j;     i < j ≤ A.length;     A[ j ] ≥ A[Left( j )] && A[ j ] ≥ A[Right( j )]             for i ← ⌊A.length/2⌋ downto 1 do Max-Heapify (A, i );

    
    

    //*@ post (\forall int j;  j ≥ 1 && j ≤ A.length;  A[ j ] ≥ A[left( j )] && A[ j ] ≥ A[right( j )]);

Running Time of Heapify (Build-Max-Heap)

• Simple Upper Bound - Applying loop analysis to get a simple upper bound:
  
  • The number of times through the loop is  ⌊n/2⌋  or O(n)
    
  • Max-Heapify T(n) = Θ(lg n)
    
  • Build-Max-Heap T(n) = O(n lg n)

    Question 6.5 - What does O(n lg n) assume in terms of the Max_Heapify tree height?

• Tighter Upper Bound
  • Build-Max-Heap running time is dependent on the height of the node it is working on.
    
  • The height of most nodes is small.

• Note the following facts:
  • height of a node is the number of edges in the longest path from that node to a leaf
    
  • full tree - each node is either a leaf or has degree exactly 2
    
  • height of n-element heap = ⌊ lg n ⌋ 
    
  • maximum number of nodes at any height h = ⌈n / 2^h+1⌉ when n = # of nodes in a full tree
    • tree above for height h = 3 is: ⌈ 15/2³⁺¹ ⌉ = 1,  height h = 0 is: ⌈15/2⁰⁺¹⌉ = 8
      
• Heapify
  • Sum up the cost of all the trips through the loop.
    
  • c*h is the cost of Max-Heapify on a node at height h

T(n) =		=
=		=
but	using formula A.8 and for x = 1/2 < 1	= 2	and O(2n) = O(n)

• Revisited Simple Upper Bound - Applying loop analysis to get a simple upper bound:
  • The number of times through the loop is  ⌊n/2⌋  or O(n)
    
  • Max-Heapify T(n) = Θ(lg n)
    
  • Build-Max-Heap T(n) = O(n lg n)

Question 6.6

We determined a simple upper bound of

T(n) = O(n lg n)

and tightened the bounds to

T(n) = O(n)

Think about what happens to the depth with each application of Max-Heapify. What simplifying assumption did we make to come up with

T(n) = O(n lg n)?