From Jason Turner

[alg.heap.operations]

C++14 → C++17 6.8 KB 97 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp8mqyut4h/{from.md → to.md} +56 -34
tmp/tmp8mqyut4h/{from.md → to.md} RENAMED
@@ -1,22 +1,15 @@
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`). Its two key properties are:
5
 
6
- - **(1)} There is no element greater than
7
- \texttt{\*a}
8
- in the range and**
9
-
10
- - **`(2)} \texttt{*a}
11
- may be removed by
12
- \texttt{pop_heap()},
13
- or a new element added by
14
- \texttt{push_heap()},
15
- in
16
- $\mathcal{O}(\log(N))$
17
- time.`**
18
 
19
  These properties make heaps useful as priority queues.
20
 
21
  `make_heap()`
22
 
@@ -32,19 +25,19 @@ template<class RandomAccessIterator>
32
  template<class RandomAccessIterator, class Compare>
33
  void push_heap(RandomAccessIterator first, RandomAccessIterator last,
34
  Compare comp);
35
  ```
36
 
37
- *Effects:* Places the value in the location `last - 1` into the
38
- resulting heap \[`first`, `last`).
39
-
40
  *Requires:* The range \[`first`, `last - 1`) shall be a valid heap. The
41
  type of `*first` shall satisfy the `MoveConstructible` requirements
42
- (Table  [[moveconstructible]]) and the `MoveAssignable` requirements
43
- (Table  [[moveassignable]]).
44
 
45
- *Complexity:* At most `log(last - first)` comparisons.
 
 
 
46
 
47
  #### `pop_heap` <a id="pop.heap">[[pop.heap]]</a>
48
 
49
  ``` cpp
50
  template<class RandomAccessIterator>
@@ -57,17 +50,17 @@ template<class RandomAccessIterator, class Compare>
57
 
58
  *Requires:* The range \[`first`, `last`) shall be a valid non-empty
59
  heap. `RandomAccessIterator` shall satisfy the requirements of
60
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
61
  shall satisfy the requirements of `MoveConstructible`
62
- (Table  [[moveconstructible]]) and of `MoveAssignable`
63
- (Table  [[moveassignable]]).
64
 
65
  *Effects:* Swaps the value in the location `first` with the value in the
66
  location `last - 1` and makes \[`first`, `last - 1`) into a heap.
67
 
68
- *Complexity:* At most `2 * log(last - first)` comparisons.
69
 
70
  #### `make_heap` <a id="make.heap">[[make.heap]]</a>
71
 
72
  ``` cpp
73
  template<class RandomAccessIterator>
@@ -76,17 +69,17 @@ template<class RandomAccessIterator>
76
  template<class RandomAccessIterator, class Compare>
77
  void make_heap(RandomAccessIterator first, RandomAccessIterator last,
78
  Compare comp);
79
  ```
80
 
81
- *Effects:* Constructs a heap out of the range \[`first`, `last`).
82
-
83
  *Requires:* The type of `*first` shall satisfy the `MoveConstructible`
84
- requirements (Table  [[moveconstructible]]) and the `MoveAssignable`
85
- requirements (Table  [[moveassignable]]).
86
 
87
- *Complexity:* At most `3 * (last - first)` comparisons.
 
 
88
 
89
  #### `sort_heap` <a id="sort.heap">[[sort.heap]]</a>
90
 
91
  ``` cpp
92
  template<class RandomAccessIterator>
@@ -95,46 +88,75 @@ template<class RandomAccessIterator>
95
  template<class RandomAccessIterator, class Compare>
96
  void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
97
  Compare comp);
98
  ```
99
 
100
- *Effects:* Sorts elements in the heap \[`first`, `last`).
101
-
102
  *Requires:* The range \[`first`, `last`) shall be a valid heap.
103
  `RandomAccessIterator` shall satisfy the requirements of
104
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
105
  shall satisfy the requirements of `MoveConstructible`
106
- (Table  [[moveconstructible]]) and of `MoveAssignable`
107
- (Table  [[moveassignable]]).
108
 
109
- *Complexity:* At most N log(N) comparisons (where `N == last - first`).
 
 
110
 
111
  #### `is_heap` <a id="is.heap">[[is.heap]]</a>
112
 
113
  ``` cpp
114
  template<class RandomAccessIterator>
115
  bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
116
  ```
117
 
118
  *Returns:* `is_heap_until(first, last) == last`
119
 
 
 
 
 
 
 
 
 
 
120
  ``` cpp
121
  template<class RandomAccessIterator, class Compare>
122
  bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
123
  ```
124
 
125
  *Returns:* `is_heap_until(first, last, comp) == last`
126
 
 
 
 
 
 
 
 
 
 
 
 
 
127
  ``` cpp
128
  template<class RandomAccessIterator>
129
  RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
 
 
 
 
130
  template<class RandomAccessIterator, class Compare>
131
  RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
132
  Compare comp);
 
 
 
 
133
  ```
134
 
135
- *Returns:* If `distance(first, last) < 2`, returns `last`. Otherwise,
136
- returns the last iterator `i` in \[`first`, `last`\] for which the range
137
  \[`first`, `i`) is a heap.
138
 
139
  *Complexity:* Linear.
140
 
 
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
 
 
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>
 
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>
 
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>
 
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