Held: Tuesday, 12 November 2013

Back to Outline 38 - Detour: Anonymous Inner Classes. On to Outline 40 - Designing a Dictionary API.

Summary

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

Related Pages

• Reading: Priority Queues
• Lab: Prioirty Queues
• Code: https://github.com/Grinnell-CSC207/linear
• EBoard (HTML) (PDF)

Overview

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

Administrivia

• I will reserve time for questions on HW9.
• There is no reading for tomorrow. Tomorrow we start to design a new interface that we will explore for the next few weeks (up through Turkey break).
• Upcoming extra credit opportunities:
  • Town Hall, Wednesday, November 13, noon or 7:30 p.m.
  • Learning from Alumni, Thursday, 2:15: Atul Gupta, Trustee
  • CS Extra, Thursday, 4:15: Hilary Mason '00
  • Evening chat with Hilary Mason '00, Thursday, 8-9 pm
  • CS Table, Next Friday, HCI
  • Innovation Class, Friday, 12:45, ARH 302, Hilary Mason '00
  • Career Connections with Hilary Mason '00, Friday, 4:15-6:30 (???)
  • Swim meet, Saturday, noon
  • Digital Commons talk Monday, November 19, 7:00 p.m. or so
  • "Data Sovereignty: The Challenge of Geolocating Data in the Cloud", November 25, 4:15 JRC 101
  • "Gold Fever" by Andrew Sherburne '01 or so, 7:00 p.m., Monday, November 25, ARH 302
  • Tuesday, November 26, 4:15 p.m., JRC 209 a gaming event with the game [d0x3d!]

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!)