Test 2 Review Exercises

- Describe the O(NlogN) heap construction algorithm and justify its complexity.

- Describe the O(N) heap construction algorithm and justify its complexity.

- Describe the heapsort algorithm and give and justify its complexity.

- Give the search time for each structure below. Justify your answers,
and explain any assumptions you are making.
- heap

- hash table/chaining

- hash table/open addressing

- binary trie (argue that search is O(1))

- binary trie (argue that search is O(log N))

- heap