Held: Wednesday, 2 April 2014

Back to Outline 34 - Implementing Queues with Arrays. On to Outline 36 - Pause for Breath.

Summary

We consider priority queues, the third of the important linear structures.

Related Pages

• Reading: Linear Structures
• Reading: Priority Queues
• Lab: Array-based Queues
• Repository: https://github.com/Grinnell-CSC207/linear
• EBoard 35 (Source 35) (HTML 35) (PDF 35)

Overview

• A short introduction to priority queues.
• Array-based implementations.
• Running times.
• Sorting with priority queues.

Administrivia

• No writeup today!
• I will reserve time at the start of class for questions on the exam.
• No reading for Friday.
• Consider running for the SEPC.
• Extra credit:
  • Convocation, today, noon: Elizabeth Kolbert (the Sixth Extinction)
  • Technology in the liberal arts symposium on Thursday.
  • CS table Friday: The Performance Contract, which is highly relevant to this class.

A quick introduction to priority queues

• Linear structures.
• But with the policy "highest priority first".
• Priority represented with a Comparator.
• Probably easier to implement than queues, particularly if you've already studied sorting.

Implementation with arrays

• Two options:
  • Stored in order (put is slow)
  • Stored unordered (get is slow)

Run-time analysis

• Put or get is O(n).
• That's kind of disappointing. For queues and stacks, put and get were both O(1).
• Can we do better? Yes, but it requires that we learn some new concepts. So we'll return to a better implementation toward the end of the semester.

Sorting with priority queues

• Can you guess an obvious sorting algorithm?

Lab

Back to our favorite repository. (And we're not done with it yet!)