Heaps

Selection Trees
- Motivation from merge sort (HSM Ch.5.8.1)
- Winner trees (HSM Ch.5.8.2, Fig.5.31)
- Merging complexity (HSM p.301)
- Loser trees (HSM Ch.5.8.3, Fig.5.33)
Heaps
- Definition (HSM Ch.5.6.2, Fig.5.24-25)
- Heap ADT (HSM ADT 5.2, Prog.5.17)
- Insertion into a Max heap (HSM Ch.5.6.3)
- Deletion from a Max heap (HSM Ch.5.6.4)

Exercises

What application is a winner tree useful for?
Show the successive states of the following winner tree after N deletion operations.
[Picture of some winner tree and its runs, make up your own :-]
Derive, using using step counts or reasonable explanation, the asymptotic complexity of deletion from a winner tree and the following update from a run.
Define a {min,max} heap.
Give the algorithm for insertion into a {min,max} heap. What is the big-O complexity of this algorithm?
Show the successive states of the following {min,max} heap after insertion of these values [list of values to insert, one by one]
[Picture of some heap, make up your own :-]
Give the algorithm for deletion from a {min,max} heap. What is the big-O complexity of this algorithm?
Show the successive states of the following {min,max} heap after N deletion operations.
[Picture of some heap, make up your own :-]