Module 2: Heapsort

Welcome to Module 2

In this module, we will examine an additional sorting algorithm, heapsort. Heapsort relies on viewing elements of an array as if they form a tree, which is something we briefly explored in Data Structures and Algorithms. By maintaining the "heap" property of this array as values are added and removed, we can accomplish either a sorting algorithm or a priority queue.

Module Learning Outcomes

Upon successful completion of this module, you will be able to:

Store data in heap format in an array (CLO 2).
Characterize the time to build a heap empirically (CLO 3).
Use a max-heap to implement a sorting algorithm (CLO 2).

(CLO = Course Learning Outcome)

To Do

Please read/watch all of the module learning materials (readings, presentations, videos, etc.) and complete all assignments/assessments listed below. If you have questions, please contact the course instructor or ask in the Questions About This Course forum.

Readings and Presentations:

Read Chapter 6
Topic 2: Heapsort Online Lecture

Tutorials:

Loop Invariant Proofs Links to an external site. (used in Section 6.3 of book)

Animations:

Sorting Algorithms Animations (see Heap algorithm)

Assignments/Assessments:

Exercise 2: Build Heap Time

Click the Next ▶ button to continue.