CSSE 230: Session Notes - Day 15

Topics

1. Binary Heaps
2. Priority Queues
3. Heapsort

Outline

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

Resources

• A video narrating the slides for MinHeaps
• A min heap visualization
• 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