COMP2011 Tutorial Exercises 6, Week 7

Trees, Heaps

Tutorial Questions

1. R-6.14: Draw a (single) binary tree T such that

   • each internal node of T stores a single character
   • a preorder traversal of T yields EXAMFUN
   • an inorder traversal of T yields MAFXUEN

2. Illustrate the performance of the heap-sort algorithm on the following input sequence: (2,5,6,8,9,4,10,3,11,7,1). Do it both with and without "bottom-up heap construction".

3. C-7.17: Describe an algorithm that computes the kth smallest element of a set of n distinct integers in O(n + k log n) time.

4. C-7.14: Let T be a heap storing n keys. Give an efficient algorithm for reporting all the keys in T that are smaller than or equal to a given query key x (which is not necessarily in T).

5. Any questions about Assignment 2.