General

• A priority queue is a data structure that allows at least the following two operations: insert, which does the obvious thing; and deleteMin, which finds, returns, and removes the minimum element in the priority queue.
• The insert operation is the equivalent of enqueue, and deleteMin is the priority queue equivalent of the queue’s dequeue operation.
• greedy algorithms


  Operate by repeatedly finding a minimum
• PriorityQueue

  Insert, findMin, and deleteMin are expressed via calls to add, element, and remove
• The PriorityQueue can be constructed either with no parameters, a comparator, or another compatible collection
• It is unfortunate that the library designers did not choose to make PriorityQueue an interface
• deleteMin for binomial queues

  1. Find minimum index

  2. Remove minimum item

  3. Construct H''

  4. Construct H'

  5. Merge
• The leftist heap is a wonderful example of the power of recursion
• The skew heap represents a remarkable data structure because of the lack of balance criteria
• The binomial queue shows how a simple idea can be used to achieve a good time bound
• Priority queues have uses ranging from operating systems scheduling to simulation