CSE 326 – Data Structures – Winter 2002

Homework #6 – Heaps and Sorting

Due Wednesday, February 20^th, 2002

Hand in hardcopy in class

1. You are told that a “foobar” is a kind of heap for which both Insert and DeleteMin can be implemented in constant amortized time. What else do you immediately know about foobars?

2. Weiss 6.2.

3. Weiss 6.14.

4. (a) Consider an implementation of QuickSort which always uses the middle element as the pivot. Describe in English the form of input that would give W(n²) run time, and illustrate it for an array of length 10.

(b) Now suppose QuickSort uses the “median of three” rule, examining the first, middle (as defined above), and last element. Again, describe in English the form of input that would give W(n²) run time, and illustrate it for an array of length 10.

5. Weiss 7.12. Assume Floyd’s method is used to build the heap.