Reading 03

The assigned reading prior to Tuesday, February 5th is an overview of heaps, heap sort and related priority queues. We'll also ask some followup questions re: merge sort and quick sort below from the prior reading assignment now we've had some time to discuss during lecture.

Please refer to:

  1. Data Structures and Other Objects Using C++:

    • Chapter 10.1-2, 10.4 Review

    • Chapter 11.1-2

Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

  1. Data Structures & Algorithm Analysis

    • 5.5 Heaps and Priority Queues

    • 7.6 Heapsort

  2. Open Data Structures


Questions (due 2/5, 10:30am)

Once you have completed the readings, answer the following questions:

  1. What does it mean for a sorting algorithm to be stable? When is it useful to be stable?

  2. Look over the lecture notes from Dr. Plank and the discussion therein. Why do you think most real-world sorting (i.e., C++ Sort) implementations use some form of quick sort?
  3. When inserting an entry into a binary heap, we must perform reheapification. What is the purpose and complexity of this process?

Submission

To submit your reading assignment, you must upload a text/PDF file onto Canvas prior to class