COMP2011 Tutorial Exercises 6, Week 7

Trees, Heaps

Tutorial Questions

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

  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.