CS 245 Lecture 26 – Heaps and Priority Queues

Agenda

  • what ?s
  • interview questions
  • program this
  • design this
  • heaps

TODO

  • Read section 6.5 in the data structures book. 1/4 sheet.

Program This

Design This

Suppose you have a large supercomputer in your basement. To defray electricity costs, you decide to rent out processing time to scientists with large problems to solve. These scientists submit their jobs to you, and whenever some CPUs/cores are free, you consult the list of submissions and run one of them.

How do you choose which one to run? (You are an opportunist, by the way, and are ever profit-seeking.) How do you organize the data so that choosing the next job is fast?

Code

Haiku

prioriTIES
A heap won’t help me
It all seems so important
CompareTo gives naught

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *