## 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?