Priority Queues

Create a Queue that Supports Data Priority

Exploration

• Read chapter 19 in A First Course on Data Structures in Python
• Explore PriorityQueue implementations in the ds2 package of donsheehy/datastructures. Can you write tests to confirm that they preserve priority? Can you see how this data structure combines those that we previously studied?
• Review previous chapters to see how the data structures like List, Queue, and Tree support the behavior of this data structure.

Activities

• Monday and Wednesday: Priority Queues
  • Explore how to implement the PriorityQueue data structure
  • Understand how the List and Tree support implementing the PriorityQueue
  • Explore how the Heap can be used to implement the PriorityQueue
  • Examine Python source code segments to illustrate key points
• Thursday: Start a new algorithm engineering project
• Friday: Report on an algorithm all-hands project

Project

Goal

To build and use a Python program, called treesearcher, that runs benchmarks to study the performance of finding data values in a hierarchical data structure.

Steps

• Use treesearcher as your template repository
• Install the project’s dependencies using devenv
• Follow the instructions to complete the project:
  • Week 1: Implement all of the modules in treesearcher
  • Week 2: Design and conduct experiments and document experimental results
• Schedule office hours if you have questions

Slides

Full Screen: Week Fourteen: Priority Queues