tmp/tmpy48hvb17/{from.md → to.md}
RENAMED
|
@@ -0,0 +1,17 @@
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
+
#### General <a id="alg.heap.operations.general">[[alg.heap.operations.general]]</a>
|
| 2 |
+
|
| 3 |
+
A random access range \[`a`, `b`) is a *heap with respect to `comp` and
|
| 4 |
+
`proj`* for a comparator and projection `comp` and `proj` if its
|
| 5 |
+
elements are organized such that:
|
| 6 |
+
|
| 7 |
+
- With `N = b - a`, for all i, 0 < i < N,
|
| 8 |
+
`bool(invoke(comp, invoke(proj, a[\left \lfloor{\frac{i - 1}{2}}\right \rfloor]), invoke({}proj, a[i])))`
|
| 9 |
+
is `false`.
|
| 10 |
+
- `*a` may be removed by `pop_heap`, or a new element added by
|
| 11 |
+
`push_heap`, in 𝑂(log N) time.
|
| 12 |
+
|
| 13 |
+
These properties make heaps useful as priority queues.
|
| 14 |
+
|
| 15 |
+
`make_heap` converts a range into a heap and `sort_heap` turns a heap
|
| 16 |
+
into a sorted sequence.
|
| 17 |
+
|