File TreePriorityQueue.h

↰ Parent directory (ADS/priority)

The PRIORITYQUEUE [see File PriorityQueue.h] on a tree.

Definition (`ADS/priority/TreePriorityQueue.h`)

Program Listing for File TreePriorityQueue.h

Detailed Description

TreePriorityQueue is a Red-Black tree of the pairs ( priority , number of insertion ) (section 10.1.2): every operation in O( log n ).

The contracts [see File Contract.h]: min() and deleteMin() need a queue that is not empty, decrease() the handle of an item still in the queue and a priority not larger than its own; the invariant is that each item of the tree has the priority recorded for its handle. The operations are defined in TreePriorityQueue.tpp.