Heaps!

For this prefect session, we will first quickly go over:

1. Heap completeness; the Heap property  
2. Heap implementation using Arrays  
3. Min, Max Heaps  
3. Priority Queue implementation  

Then, we will attempt to solve the following:
* Which of the following is not a valid max heap?

(a)        9
            \
             2 
(b)        4
          /  \
          9   6
         / \ / 
        2  7 10  
(c)       12
         /  \
        12   6
       / \  / \
      5   8 2  4
     /
     4
(d)       12
         /  \
        12   6
       / \  / \
      5   8 2  4
     /
     8
(e)       12
         /  \
        12   6
       / \  / \
      5   8 2  4
     /     \
     5     84
 (f)      12
         /  \
        12   6
       / \  / \
      5   8 2  4
     /     \
     5     11
 (g)      14
         /  \
        11   15
       / \  /  \
      5   8 2   4
     /   / \
     5   2  20 
  • For any of the heaps in (1) that is not valid, can you apply any finite number of appropriate number of heap operations (bubbleDown, bubbleUp, and so on) to make it valid? If so, make it valid by making each subtree -- starting from the leaves -- a valid heap.

  • Perform heapsort on the following arrays clearly showing how the heap changes at each stage:

A = [1,9,8,7,6,5,4,3,2]  
B = [15,20,1,50,1,2]  
  • Heapsort takes $\Theta(n\log n)$. Mergesort asymptotically has the same runtime. Why would we use one over the other?