CSC236 Data Structures - Problem Set: Heaps

Problem Set: Heaps

For each of the following, tell whether it's a minheap, a maxheap, or not a valid heap. If it's not a heap, explain why.

Build a minheap from the following values. Show the heap after inserting 5 values, 10 values, 15 values, and after inserting all values.
```
  64 25 81 36 16 144 9 100 75 12 225 269 121 196 49 94 135
```
Build a maxheap from the following values. Show the heap after inserting 5 values, 10 values, 15 values, and after inserting all values.
```
  97 59 31 144 49 81 256 36 16 169 55 121 269 25 100 64 86
```
Build a maxheap from the following values. Show the heap after inserting 5 values, 10 values, 15 values, and after inserting all values.
```
  100 50 300 150 75 125 25 400 250 200 350 175 65 225 425 115 275 375 185 90
```
Build a minheap from the following values. Show the heap after inserting 5 values, 10 values, 15 values, and after inserting all values.
```
  150 50 300 100 225 75 400 275 200 25 125 350 250 175 90 425 375 115 185 65
```
Remove 8 values from the following heap (remove the root each time). Show the heap after each value is removed.
Consider the heap from the problem above. Show how it will be stored in an array. Use the heap as shown, not after you deleted from it.
Remove 8 values from the following heap (remove the root each time). Show the heap after each value is removed.
Consider the heap from the problem above. Show how it will be stored in an array. Use the heap as shown, not after you deleted from it.
Given the following heap:
```
360  305  275  242  290  260  150  99   175  230  140  180  250  120
[0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10] [11] [12] [13]
```
1. What is the left child of 242?
2. What is the right child of 260?
3. Does 150 have a left child? If so what is it?
4. Does 150 have a right child? If so what is it?
5. Draw the heap
Show the array from problem 9 after one pass of heapsort (move one element to the end and then perform siftdown).
Show the array from problem 9 after a second pass of heapsort (move one element to the end and then perform siftdown).
Show the array from problem 9 after a third pass of heapsort (move one element to the end and then perform siftdown).
Show the array from problem 9 after a fourth pass of heapsort (move one element to the end and then perform siftdown).
Show the array from problem 9 after a fifth pass of heapsort (move one element to the end and then perform siftdown).
Show the array from problem 9 after a sixth pass of heapsort (move one element to the end and then perform siftdown).