Module: Heapsort

Heaps, correctness, run-time analysis, priority queues, application to sorting.

Learning Outcomes

Characterize behavior of heaps, heapsort, and priority queues, including:

Characterize the asymptotic running time of heap algorithms.
Define and implement various operations on heaps.

Readings

Introduction to heaps

Basic ideas about heaps

Screencast Suthers 14 min

Building heaps

Understanding how to build heaps

Screencast Suthers 14 min

Analyzing heap building

Correctness and run time analysis of heaps

Screencast Suthers 9 min

Applications of heaps

Heapsort and priority queues

Screencast Suthers 14 min

CLRS 6 - Heapsort

Heapsort, heaps, maintaining the heap property, building a heap, priority queues

Textbook 19 pages

Chapter 9 Notes

Notes on heaps and heapsort.

Notes

Experiential Learning

Applying your understanding of heaps (again)

Learn about heaps (at home).

Homework