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:
Data Structures and Other Objects Using C++:
Chapter 10.1-2, 10.4 Review
Chapter 11.1-2
If you do not have the primary textbook, you can use the following free alternative texts instead:
Data Structures & Algorithm Analysis
5.5 Heaps and Priority Queues
7.6 Heapsort
Once you have completed the readings, answer the following questions:
What does it mean for a sorting algorithm to be stable? When is it useful to be stable?
For merge sort and quick sort, explain whether or not the algorithm is considered stable.
When inserting an entry into a binary heap, we must perform reheapification. What is the purpose and complexity of this process?
To submit your reading assignment, you must upload a text/PDF file onto Canvas prior to class