Reading 03: Priority Queues, Heaps, Sorting

Readings

The readings for Monday, September 12 are:

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

   • Chapter 10.1-2, 10.4 Review

   • Chapter 11.1 - 2, 11.4

   • Chapter 13.1, 13.3

2. VisuAlgo - Sorting

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.1 Sorting Terminology and Notation

   • 7.2 Three O(n^2) Sorting Algorithms

   • 7.6 Heapsort

2. Open Data Structures

   • 10. Heaps

   • 11.1.3 Heap-sort

Questions

Once you have completed the readings, answer the following questions in the reading03/README.md file in your assignments repository:

1. Identify which of the following trees is a maximum binary heap? If a tree is not a maximum binary heap, explain why.

   

2. When inserting an entry into a binary heap, we must perform reheapification. What is the purpose and complexity of this process?

3. Trace the execution of selection sort for an array containing {9, 6, 0, 0, 7}. That is show the contents of the array after each iteration of the sorting algorithm.

4. Trace the execution of insertion sort for an array containing {9, 6, 0, 0, 7}. That is show the contents of the array after each iteration of the sorting algorithm.

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 03 - TA assignment list.

$ cd path/to/repo                 # Go to your repository
$ git checkout master             # Make sure we are on master branch first
$ git pull                        # Make sure we have changes from GitLab
$ git checkout -b reading03       # Create reading03 branch
...                               # Do your work
$ git commit                      # Commit your work (can do this multiple times)
$ git push -u origin reading03    # Push branch to GitLab