Chapter 6 - Heaps

Definition

A heap can be defined as a binary tree with one key (value) assigned to each node provided the following two requirements are met:

1. Tree shape - the binary tree is essentially complete; all levels are full except possibly the last level where only some rightmost leaves are missing.
2. Parental dominance - the key at each node is greater than or equal the keys of the children; this is satisfied automatically for leaf nodes.

         a.                                                b.                                    c.

Question 6.1 - Which of these trees satisfy the heap definition? Why not?

 

Note that a heap is not necessarily sorted.

Heap data structure

• Heap as a binary tree

  height of node - number of edges on a longest simple path from node down to a leaf.

  height of heap - height of root = Θ(lg n)

• In general, can be an n-ary tree.
   
• Max Heap A below can be stored as array A at right.
  • Root at A[1]
     
  • Parent of A[i] = A[ ⌊i/2⌋ ]
     
  • Left child of A[i] = A[2i]
     
  • Right child of A[i] = A[2i + 1]
     
  • For A[i]
                           Parent
                         A[ ⌊i/2⌋ ]
     Left child                           Right child
       A[2i]                                A[2i + 1]

Question 6.2 Do the arithmetic to determine the array index number of:

1. parent of A[9]
    
2. left child of A[2]
    
3. right child of A[2]

• Max-heap satisfies the parental dominance property

  A[ ⌊i/2⌋ ] ≥ A[i]                            i.e. A[ Parent(i) ] ≥ A[i]

Question 6.3 What array index holds the largest element in a max-heap?

                The smallest?

                The max-heap below has height 3. What size array would be required if the max-heap below were full?

                How many array entries for a max-heap of height h?

Example of a max-heap, meaning A[ ⌊i/2⌋ ] ≥ A[i]; that is: A[ Parent(i) ] ≥ A[ Left(i) ] && A[ Parent(i) ] ≥ A[ Right(i) ]

Max Heap properties

1. There exists exactly one essentially complete binary tree with n nodes; its height = ⌊lg n ⌋
   

2. The root of the tree always contains the largest key.
    

3. The root of any subtree and descendents is also a heap; the subtree root always contains the largest key of the heap.
    

4. A heap can be implemented as an array by recording its elements in top-down left-to-right fashion. Starting at index 1:

   1. parent nodes occupy the first ⌊n/2⌋ positions of the array; leaf nodes will occupy the last  ⌈n/2⌉  positions.
       

   2. for parent position i (1 ≤ i ≤  ⌊n/2⌋ ), the left child will be at array position 2i and right child at position 2i+1

   For array A:

   Parent of A[i] = A[ ⌊i/2⌋ ]

   Left child of A[i] = A[ 2i ]

   Right child of A[i] = A[ 2i + 1 ]