Unit 12 -- Csc 115 Spring 2005 SO1/S02
Learning Objectives for this unit
- To learn how to use and create priority queues
- Know how to implement them using linked lists (sequences) and arrays.
- Understand the selection sort and insertion sort algorithms and their efficiency.
- Know how to implement priority queues using a heap data structure
- Understand the heap sort algorithm and its efficiency
- Understand the efficiency concerns of the different implementations
- Know how to do a Bottom up heap construction
Learning Resources for this week
Lecture slides:
12-PriorityQueues.ppt
Code examples (do the exercises!):
The following websites contain animations which may help:
Reading Assignment:
Read Chapter 7 (you can omit 7.4)
Activities:
True/False Questions
- You can implement a priority queue using a linked list, array or a heap.
From this choice, the most efficient implementation for a priority queue is a linked list. T/F
- The running time of selection sort is O( n log n). T/F
- The running time of the insertion sort is O(n^2). T/F
- The running time of the Heapsort algorithm is O(n^2). T/F
Problems in the textbook, Chapter 7:
- R-7.1
- R-7.3
- R-7.4
- R-7.5
- R-7.6
- R-7.8
- R-7.9
- R-7.10
- C-7.4
- C-7.5
Code exercises
Remember to check out the exercises embedded in the posted
examples above for this unit.
Go to the course website