High Level Data Structure A collection of priority-job pairs. Priority is comparable Can insert(p, j) to insert job j with priority p Can return max() job with max priority Can extract-max(): remove and return job with max priority Implementations Min-Heap Max-Heap