From Jason Turner

[alg.heap.operations]

C++17 → C++20 13.8 KB 223 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpymicwrdx/{from.md → to.md} +160 -60
tmp/tmpymicwrdx/{from.md → to.md} RENAMED
@@ -1,162 +1,262 @@
1
  ### Heap operations <a id="alg.heap.operations">[[alg.heap.operations]]</a>
2
 
3
- A *heap* is a particular organization of elements in a range between two
4
- random access iterators \[`a`, `b`) such that:
 
5
 
6
  - With `N = b - a`, for all i, 0 < i < N,
7
- `comp(a[\left \lfloor{\frac{i - 1}{2}}\right \rfloor], a[i])` is
8
- `false`.
9
- - `*a` may be removed by `pop_heap()`, or a new element added by
10
- `push_heap()`, in 𝑂(log N) time.
11
 
12
  These properties make heaps useful as priority queues.
13
 
14
- `make_heap()`
15
-
16
- converts a range into a heap and `sort_heap()` turns a heap into a
17
- sorted sequence.
18
 
19
  #### `push_heap` <a id="push.heap">[[push.heap]]</a>
20
 
21
  ``` cpp
22
  template<class RandomAccessIterator>
23
- void push_heap(RandomAccessIterator first, RandomAccessIterator last);
24
 
25
  template<class RandomAccessIterator, class Compare>
26
- void push_heap(RandomAccessIterator first, RandomAccessIterator last,
27
  Compare comp);
 
 
 
 
 
 
 
 
 
 
28
  ```
29
 
30
- *Requires:* The range \[`first`, `last - 1`) shall be a valid heap. The
31
- type of `*first` shall satisfy the `MoveConstructible` requirements
32
- (Table  [[tab:moveconstructible]]) and the `MoveAssignable` requirements
33
- (Table  [[tab:moveassignable]]).
 
 
 
 
34
 
35
  *Effects:* Places the value in the location `last - 1` into the
36
  resulting heap \[`first`, `last`).
37
 
38
- *Complexity:* At most log(`last - first`) comparisons.
 
 
 
39
 
40
  #### `pop_heap` <a id="pop.heap">[[pop.heap]]</a>
41
 
42
  ``` cpp
43
  template<class RandomAccessIterator>
44
- void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
45
 
46
  template<class RandomAccessIterator, class Compare>
47
- void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
48
  Compare comp);
 
 
 
 
 
 
 
 
 
 
49
  ```
50
 
51
- *Requires:* The range \[`first`, `last`) shall be a valid non-empty
52
- heap. `RandomAccessIterator` shall satisfy the requirements of
53
- `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
54
- shall satisfy the requirements of `MoveConstructible`
55
- (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
56
- (Table  [[tab:moveassignable]]).
 
 
 
57
 
58
  *Effects:* Swaps the value in the location `first` with the value in the
59
- location `last - 1` and makes \[`first`, `last - 1`) into a heap.
 
60
 
61
- *Complexity:* At most 2 log(`last - first`) comparisons.
 
 
 
62
 
63
  #### `make_heap` <a id="make.heap">[[make.heap]]</a>
64
 
65
  ``` cpp
66
  template<class RandomAccessIterator>
67
- void make_heap(RandomAccessIterator first, RandomAccessIterator last);
68
 
69
  template<class RandomAccessIterator, class Compare>
70
- void make_heap(RandomAccessIterator first, RandomAccessIterator last,
71
  Compare comp);
 
 
 
 
 
 
 
 
 
 
72
  ```
73
 
74
- *Requires:* The type of `*first` shall satisfy the `MoveConstructible`
75
- requirements (Table  [[tab:moveconstructible]]) and the `MoveAssignable`
76
- requirements (Table  [[tab:moveassignable]]).
77
 
78
- *Effects:* Constructs a heap out of the range \[`first`, `last`).
 
 
 
79
 
80
- *Complexity:* At most 3(`last - first`) comparisons.
 
 
 
 
 
 
81
 
82
  #### `sort_heap` <a id="sort.heap">[[sort.heap]]</a>
83
 
84
  ``` cpp
85
  template<class RandomAccessIterator>
86
- void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
87
 
88
  template<class RandomAccessIterator, class Compare>
89
- void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
90
  Compare comp);
 
 
 
 
 
 
 
 
 
 
91
  ```
92
 
93
- *Requires:* The range \[`first`, `last`) shall be a valid heap.
94
- `RandomAccessIterator` shall satisfy the requirements of
95
- `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
96
- shall satisfy the requirements of `MoveConstructible`
97
- (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
98
- (Table  [[tab:moveassignable]]).
99
 
100
- *Effects:* Sorts elements in the heap \[`first`, `last`).
 
 
 
 
 
101
 
102
- *Complexity:* At most N log N comparisons, where N = `last - first`.
 
 
 
 
 
 
103
 
104
  #### `is_heap` <a id="is.heap">[[is.heap]]</a>
105
 
106
  ``` cpp
107
  template<class RandomAccessIterator>
108
- bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
109
  ```
110
 
111
- *Returns:* `is_heap_until(first, last) == last`
112
 
113
  ``` cpp
114
  template<class ExecutionPolicy, class RandomAccessIterator>
115
  bool is_heap(ExecutionPolicy&& exec,
116
  RandomAccessIterator first, RandomAccessIterator last);
117
  ```
118
 
119
- *Returns:*
120
- `is_heap_until(std::forward<ExecutionPolicy>(exec), first, last) == last`
 
 
 
121
 
122
  ``` cpp
123
  template<class RandomAccessIterator, class Compare>
124
- bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
125
  ```
126
 
127
- *Returns:* `is_heap_until(first, last, comp) == last`
 
128
 
129
  ``` cpp
130
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
131
  bool is_heap(ExecutionPolicy&& exec,
132
- RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
133
  ```
134
 
135
- *Returns:*
136
 
137
  ``` cpp
138
- is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
139
  ```
140
 
 
 
 
 
 
 
 
 
 
 
 
 
141
  ``` cpp
142
  template<class RandomAccessIterator>
143
- RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
 
144
  template<class ExecutionPolicy, class RandomAccessIterator>
145
- RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
 
146
  RandomAccessIterator first, RandomAccessIterator last);
147
 
148
  template<class RandomAccessIterator, class Compare>
149
- RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
 
150
  Compare comp);
151
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
152
- RandomAccessIterator is_heap_until(ExecutionPolicy&& exec,
 
153
  RandomAccessIterator first, RandomAccessIterator last,
154
  Compare comp);
 
 
 
 
 
 
 
 
155
  ```
156
 
157
- *Returns:* If `(last - first) < 2`, returns `last`. Otherwise, returns
158
- the last iterator `i` in \[`first`, `last`\] for which the range
159
- \[`first`, `i`) is a heap.
 
 
160
 
161
  *Complexity:* Linear.
162
 
 
1
  ### Heap operations <a id="alg.heap.operations">[[alg.heap.operations]]</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
 
18
  #### `push_heap` <a id="push.heap">[[push.heap]]</a>
19
 
20
  ``` cpp
21
  template<class RandomAccessIterator>
22
+ constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last);
23
 
24
  template<class RandomAccessIterator, class Compare>
25
+ constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last,
26
  Compare comp);
27
+
28
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
29
+ class Proj = identity>
30
+ requires sortable<I, Comp, Proj>
31
+ constexpr I
32
+ ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {});
33
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
34
+ requires sortable<iterator_t<R>, Comp, Proj>
35
+ constexpr borrowed_iterator_t<R>
36
+ ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {});
37
  ```
38
 
39
+ Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
40
+ no parameters by those names.
41
+
42
+ *Preconditions:* The range \[`first`, `last - 1`) is a valid heap with
43
+ respect to `comp` and `proj`. For the overloads in namespace `std`, the
44
+ type of `*first` meets the *Cpp17MoveConstructible* requirements
45
+ ([[cpp17.moveconstructible]]) and the *Cpp17MoveAssignable*
46
+ requirements ([[cpp17.moveassignable]]).
47
 
48
  *Effects:* Places the value in the location `last - 1` into the
49
  resulting heap \[`first`, `last`).
50
 
51
+ *Returns:* `last` for the overloads in namespace `ranges`.
52
+
53
+ *Complexity:* At most log(`last - first`) comparisons and twice as many
54
+ projections.
55
 
56
  #### `pop_heap` <a id="pop.heap">[[pop.heap]]</a>
57
 
58
  ``` cpp
59
  template<class RandomAccessIterator>
60
+ constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
61
 
62
  template<class RandomAccessIterator, class Compare>
63
+ constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
64
  Compare comp);
65
+
66
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
67
+ class Proj = identity>
68
+ requires sortable<I, Comp, Proj>
69
+ constexpr I
70
+ ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {});
71
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
72
+ requires sortable<iterator_t<R>, Comp, Proj>
73
+ constexpr borrowed_iterator_t<R>
74
+ ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {});
75
  ```
76
 
77
+ Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
78
+ no parameters by those names.
79
+
80
+ *Preconditions:* The range \[`first`, `last`) is a valid non-empty heap
81
+ with respect to `comp` and `proj`. For the overloads in namespace `std`,
82
+ `RandomAccessIterator` meets the *Cpp17ValueSwappable*
83
+ requirements [[swappable.requirements]] and the type of `*first` meets
84
+ the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
85
+ *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
86
 
87
  *Effects:* Swaps the value in the location `first` with the value in the
88
+ location `last - 1` and makes \[`first`, `last - 1`) into a heap with
89
+ respect to `comp` and `proj`.
90
 
91
+ *Returns:* `last` for the overloads in namespace `ranges`.
92
+
93
+ *Complexity:* At most 2 log(`last - first`) comparisons and twice as
94
+ many projections.
95
 
96
  #### `make_heap` <a id="make.heap">[[make.heap]]</a>
97
 
98
  ``` cpp
99
  template<class RandomAccessIterator>
100
+ constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);
101
 
102
  template<class RandomAccessIterator, class Compare>
103
+ constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last,
104
  Compare comp);
105
+
106
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
107
+ class Proj = identity>
108
+ requires sortable<I, Comp, Proj>
109
+ constexpr I
110
+ ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {});
111
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
112
+ requires sortable<iterator_t<R>, Comp, Proj>
113
+ constexpr borrowed_iterator_t<R>
114
+ ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {});
115
  ```
116
 
117
+ Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
118
+ no parameters by those names.
 
119
 
120
+ *Preconditions:* For the overloads in namespace `std`, the type of
121
+ `*first` meets the *Cpp17MoveConstructible*
122
+ ([[cpp17.moveconstructible]]) and *Cpp17MoveAssignable*
123
+ ([[cpp17.moveassignable]]) requirements.
124
 
125
+ *Effects:* Constructs a heap with respect to `comp` and `proj` out of
126
+ the range \[`first`, `last`).
127
+
128
+ *Returns:* `last` for the overloads in namespace `ranges`.
129
+
130
+ *Complexity:* At most 3(`last - first`) comparisons and twice as many
131
+ projections.
132
 
133
  #### `sort_heap` <a id="sort.heap">[[sort.heap]]</a>
134
 
135
  ``` cpp
136
  template<class RandomAccessIterator>
137
+ constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
138
 
139
  template<class RandomAccessIterator, class Compare>
140
+ constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
141
  Compare comp);
142
+
143
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
144
+ class Proj = identity>
145
+ requires sortable<I, Comp, Proj>
146
+ constexpr I
147
+ ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {});
148
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
149
+ requires sortable<iterator_t<R>, Comp, Proj>
150
+ constexpr borrowed_iterator_t<R>
151
+ ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {});
152
  ```
153
 
154
+ Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
155
+ no parameters by those names.
 
 
 
 
156
 
157
+ *Preconditions:* The range \[`first`, `last`) is a valid heap with
158
+ respect to `comp` and `proj`. For the overloads in namespace `std`,
159
+ `RandomAccessIterator` meets the *Cpp17ValueSwappable*
160
+ requirements [[swappable.requirements]] and the type of `*first` meets
161
+ the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
162
+ *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
163
 
164
+ *Effects:* Sorts elements in the heap \[`first`, `last`) with respect to
165
+ `comp` and `proj`.
166
+
167
+ *Returns:* `last` for the overloads in namespace `ranges`.
168
+
169
+ *Complexity:* At most 2N log N comparisons, where N = `last - first`,
170
+ and twice as many projections.
171
 
172
  #### `is_heap` <a id="is.heap">[[is.heap]]</a>
173
 
174
  ``` cpp
175
  template<class RandomAccessIterator>
176
+ constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
177
  ```
178
 
179
+ *Effects:* Equivalent to: `return is_heap_until(first, last) == last;`
180
 
181
  ``` cpp
182
  template<class ExecutionPolicy, class RandomAccessIterator>
183
  bool is_heap(ExecutionPolicy&& exec,
184
  RandomAccessIterator first, RandomAccessIterator last);
185
  ```
186
 
187
+ *Effects:* Equivalent to:
188
+
189
+ ``` cpp
190
+ return is_heap_until(std::forward<ExecutionPolicy>(exec), first, last) == last;
191
+ ```
192
 
193
  ``` cpp
194
  template<class RandomAccessIterator, class Compare>
195
+ constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
196
+ Compare comp);
197
  ```
198
 
199
+ *Effects:* Equivalent to:
200
+ `return is_heap_until(first, last, comp) == last;`
201
 
202
  ``` cpp
203
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
204
  bool is_heap(ExecutionPolicy&& exec,
205
+ RandomAccessIterator first, RandomAccessIterator last,
206
+ Compare comp);
207
  ```
208
 
209
+ *Effects:* Equivalent to:
210
 
211
  ``` cpp
212
+ return is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last;
213
  ```
214
 
215
+ ``` cpp
216
+ template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
217
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
218
+ constexpr bool ranges::is_heap(I first, S last, Comp comp = {}, Proj proj = {});
219
+ template<random_access_range R, class Proj = identity,
220
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
221
+ constexpr bool ranges::is_heap(R&& r, Comp comp = {}, Proj proj = {});
222
+ ```
223
+
224
+ *Effects:* Equivalent to:
225
+ `return ranges::is_heap_until(first, last, comp, proj) == last;`
226
+
227
  ``` cpp
228
  template<class RandomAccessIterator>
229
+ constexpr RandomAccessIterator
230
+ is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
231
  template<class ExecutionPolicy, class RandomAccessIterator>
232
+ RandomAccessIterator
233
+ is_heap_until(ExecutionPolicy&& exec,
234
  RandomAccessIterator first, RandomAccessIterator last);
235
 
236
  template<class RandomAccessIterator, class Compare>
237
+ constexpr RandomAccessIterator
238
+ is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
239
  Compare comp);
240
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
241
+ RandomAccessIterator
242
+ is_heap_until(ExecutionPolicy&& exec,
243
  RandomAccessIterator first, RandomAccessIterator last,
244
  Compare comp);
245
+
246
+ template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
247
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
248
+ constexpr I ranges::is_heap_until(I first, S last, Comp comp = {}, Proj proj = {});
249
+ template<random_access_range R, class Proj = identity,
250
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
251
+ constexpr borrowed_iterator_t<R>
252
+ ranges::is_heap_until(R&& r, Comp comp = {}, Proj proj = {});
253
  ```
254
 
255
+ Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
256
+ no parameters by those names.
257
+
258
+ *Returns:* The last iterator `i` in \[`first`, `last`\] for which the
259
+ range \[`first`, `i`) is a heap with respect to `comp` and `proj`.
260
 
261
  *Complexity:* Linear.
262