CSSE 230: Session Notes - Day 14

Topics

1. Priority queues
2. Heapsort

Outline

1. [5 min] Contact before work
2. [5 min] Priority queues and their uses.
3. [5 min] Implementing a priority queue
4. [10 min] Informal analysis of Binary Heap operations
5. [15 min] Group exercise: Analyze the methods in the following implementation of a PriorityQueue
6. [15 min] Heap sort
7. [5 min] Break
8. [25 min] Analysis of heap sort: best, worst, average case
9. [Balance of time] Start work on Priority queue

Resources

• A CS use of a priority queue.
• A video narrating the slides for the first phase of heap-sort, that of building a heap
• A video narrating the slides for the second phase of heap-sort, that of repeatedly polling the max heap
• A video explaining the options for implementing a priority queue