» CS 245 Lecture 26 – Heaps and Priority Queues

CS 245 Lecture 26 – Heaps and Priority Queues

December 5, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

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

http://youtu.be/wt3Y3aXKQ0Y?t=3m37s

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