teaching machines

CS 245 Lecture 26 – Heaps and Priority Queues

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



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?



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