A partial order compares only the pairs that need comparison. It preserves reflexivity, antisymmetry, and transitivity without requiring every pair to be ordered. section 2.3.1 section 3.3
Use a partial order when the consumer needs the next highest-priority item rather than a completely sorted collection. A priority queue can therefore avoid maintaining unnecessary ordering and support operations in logarithmic time. section 2.3.1
A partial order appears in several data-structure constraints:
- A heap orders each parent against its descendants along paths, while sibling priorities remain unordered. section 3.3
- A treap combines total ordering for binary-search-tree keys with partial ordering for heap priorities. section 3.3
- The highest-priority element remains accessible at the root, even though priorities cannot support equally direct arbitrary queries. section 3.3
Task scheduling
Suppose tasks are consumed one at a time. Keeping the entire task list sorted wastes resources if only the next highest-priority task matters; a priority queue preserves the needed partial ordering instead. section 2.3.1
Figure 3.2 An example of a treap, with strings as BST keys and integers as heap priorities. Note that the heap, in this case, is a min-heap, so smaller numbers go on top. For a few links close to the root, we also show the range of keys that can be hosted in the tree’s branch rooted at the node they point to.
A treap diagram makes the two simultaneous orderings visible: names progress according to binary-search-tree keys, while smaller min-heap priorities rise toward the root. section 3.3
