tlx
Loading...
Searching...
No Matches
d_ary_addressable_int_heap.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/container/d_ary_addressable_int_heap.hpp
3 *
4 * Part of tlx - http://panthema.net/tlx
5 *
6 * Copyright (C) 2019 Eugenio Angriman <angrimae@hu-berlin.de>
7 * Copyright (C) 2019 Timo Bingmann <tb@panthema.net>
8 *
9 * All rights reserved. Published under the Boost Software License, Version 1.0
10 ******************************************************************************/
11
12#ifndef TLX_CONTAINER_D_ARY_ADDRESSABLE_INT_HEAP_HEADER
13#define TLX_CONTAINER_D_ARY_ADDRESSABLE_INT_HEAP_HEADER
14
15#include <cassert>
16#include <cstddef>
17#include <functional>
18#include <limits>
19#include <queue>
20#include <vector>
21
22namespace tlx {
23
24//! \addtogroup tlx_container
25//! \{
26
27/*!
28 * This class implements an addressable integer priority queue, precisely a
29 * d-ary heap.
30 *
31 * Keys must be unique unsigned integers. The addressable heap holds an array
32 * indexed by the keys, hence it requires a multiple of the highest integer key
33 * as space!
34 *
35 * \tparam KeyType Has to be an unsigned integer type.
36 * \tparam Arity A positive integer.
37 * \tparam Compare Function object.
38 */
39template <typename KeyType, unsigned Arity = 2,
40 class Compare = std::less<KeyType> >
42{
43 static_assert(std::numeric_limits<KeyType>::is_integer &&
44 !std::numeric_limits<KeyType>::is_signed,
45 "KeyType must be an unsigned integer type.");
46 static_assert(Arity, "Arity must be greater than zero.");
47
48public:
49 using key_type = KeyType;
50 using compare_type = Compare;
51
52 static constexpr size_t arity = Arity;
53
54protected:
55 //! Cells in the heap.
56 std::vector<key_type> heap_;
57
58 //! Positions of the keys in the heap vector.
59 std::vector<key_type> handles_;
60
61 //! Compare function.
63
64 //! Marks a key that is not in the heap.
65 static constexpr key_type not_present() {
66 return static_cast<key_type>(-1);
67 }
68
69public:
70 //! Allocates an empty heap.
72 : heap_(0), handles_(0), cmp_(cmp) { }
73
74 //! Allocates space for \c new_size items.
75 void reserve(size_t new_size) {
76 if (handles_.size() < new_size) {
77 handles_.resize(new_size, not_present());
78 heap_.reserve(new_size);
79 }
80 }
81
82 //! Copy.
85
86 //! Move.
89
90 //! Empties the heap.
91 void clear() {
92 std::fill(handles_.begin(), handles_.end(), not_present());
93 heap_.clear();
94 }
95
96 //! Returns the number of items in the heap.
97 size_t size() const noexcept { return heap_.size(); }
98
99 //! Returns the capacity of the heap.
100 size_t capacity() const noexcept { return heap_.capacity(); }
101
102 //! Returns true if the heap has no items, false otherwise.
103 bool empty() const noexcept { return heap_.empty(); }
104
105 //! Inserts a new item.
106 void push(const key_type& new_key) {
107 // Avoid to add the key that we use to mark non present keys.
108 assert(new_key != not_present());
109 if (new_key >= handles_.size()) {
110 handles_.resize(new_key + 1, not_present());
111 }
112 else {
113 assert(handles_[new_key] == not_present());
114 }
115
116 // Insert the new item at the end of the heap.
117 handles_[new_key] = static_cast<key_type>(heap_.size());
118 heap_.push_back(new_key);
119 sift_up(heap_.size() - 1);
120 }
121
122 //! Inserts a new item.
123 void push(key_type&& new_key) {
124 // Avoid to add the key that we use to mark non present keys.
125 assert(new_key != not_present());
126 if (new_key >= handles_.size()) {
127 handles_.resize(new_key + 1, not_present());
128 }
129 else {
130 assert(handles_[new_key] == not_present());
131 }
132
133 // Insert the new item at the end of the heap.
134 handles_[new_key] = static_cast<key_type>(heap_.size());
135 heap_.push_back(std::move(new_key));
136 sift_up(heap_.size() - 1);
137 }
138
139 //! Removes the item with key \c key.
140 void remove(key_type key) {
141 assert(contains(key));
142 key_type h = handles_[key];
143 std::swap(heap_[h], heap_.back());
144 handles_[heap_[h]] = h;
145 handles_[heap_.back()] = not_present();
146 heap_.pop_back();
147 // If we did not remove the last item in the heap vector.
148 if (h < size()) {
149 if (h && cmp_(heap_[h], heap_[parent(h)])) {
150 sift_up(h);
151 }
152 else {
153 sift_down(h);
154 }
155 }
156 }
157
158 //! Returns the top item.
159 const key_type& top() const noexcept {
160 assert(!empty());
161 return heap_[0];
162 }
163
164 //! Removes the top item.
165 void pop() { remove(heap_[0]); }
166
167 //! Removes and returns the top item.
169 key_type top_item = top();
170 pop();
171 return top_item;
172 }
173
174 //! Rebuilds the heap.
175 void update_all() {
176 heapify();
177 }
178
179 /*!
180 * Updates the priority queue after the priority associated to the item with
181 * key \c key has been changed; if the key \c key is not present in the
182 * priority queue, it will be added.
183 *
184 * Note: if not called after a priority is changed, the behavior of the data
185 * structure is undefined.
186 */
187 void update(key_type key) {
188 if (key >= handles_.size() || handles_[key] == not_present()) {
189 push(key);
190 }
191 else if (handles_[key] &&
192 cmp_(heap_[handles_[key]], heap_[parent(handles_[key])])) {
193 sift_up(handles_[key]);
194 }
195 else {
196 sift_down(handles_[key]);
197 }
198 }
199
200 //! Returns true if the key \c key is in the heap, false otherwise.
201 bool contains(key_type key) const {
202 return key < handles_.size() ? handles_[key] != not_present() : false;
203 }
204
205 //! Builds a heap from a container.
206 template <class InputIterator>
207 void build_heap(InputIterator first, InputIterator last) {
208 heap_.assign(first, last);
209 heapify();
210 }
211
212 //! Builds a heap from the vector \c keys. Items of \c keys are copied.
213 void build_heap(const std::vector<key_type>& keys) {
214 heap_.resize(keys.size());
215 std::copy(keys.begin(), keys.end(), heap_.begin());
216 heapify();
217 }
218
219 //! Builds a heap from the vector \c keys. Items of \c keys are moved.
220 void build_heap(std::vector<key_type>&& keys) {
221 if (!empty())
222 heap_.clear();
223 heap_ = std::move(keys);
224 heapify();
225 }
226
227 //! For debugging: runs a BFS from the root node and verifies that the heap
228 //! property is respected.
230 if (empty()) {
231 return true;
232 }
233 std::vector<unsigned char> mark(handles_.size());
234 std::queue<size_t> q;
235 // Explore from the root.
236 q.push(0);
237 // mark first value as seen
238 mark.at(heap_[0]) = 1;
239 while (!q.empty()) {
240 size_t s = q.front();
241 q.pop();
242 size_t l = left(s);
243 for (size_t i = 0; i < arity && l < heap_.size(); ++i) {
244 // check that the priority of the children is not strictly less
245 // than their parent.
246 if (cmp_(heap_[l], heap_[s]))
247 return false;
248 // check handle
249 if (handles_[heap_[l]] != l)
250 return false;
251 // mark value as seen
252 mark.at(heap_[l]) = 1;
253 q.push(l++);
254 }
255 }
256 // check not_present handles
257 for (size_t i = 0; i < mark.size(); ++i) {
258 if (mark[i] != (handles_[i] != not_present()))
259 return false;
260 }
261 return true;
262 }
263
264private:
265 //! Returns the position of the left child of the node at position \c k.
266 size_t left(size_t k) const { return arity * k + 1; }
267
268 //! Returns the position of the parent of the node at position \c k.
269 size_t parent(size_t k) const { return (k - 1) / arity; }
270
271 //! Pushes the node at position \c k up until either it becomes the root or
272 //! its parent has lower or equal priority.
273 void sift_up(size_t k) {
274 key_type value = std::move(heap_[k]);
275 size_t p = parent(k);
276 while (k > 0 && !cmp_(heap_[p], value)) {
277 heap_[k] = std::move(heap_[p]);
278 handles_[heap_[k]] = k;
279 k = p, p = parent(k);
280 }
281 handles_[value] = k;
282 heap_[k] = std::move(value);
283 }
284
285 //! Pushes the item at position \c k down until either it becomes a leaf or
286 //! all its children have higher priority
287 void sift_down(size_t k) {
288 key_type value = std::move(heap_[k]);
289 while (true) {
290 size_t l = left(k);
291 if (l >= heap_.size()) {
292 break;
293 }
294 // Get the min child.
295 size_t c = l;
296 size_t right = std::min(heap_.size(), c + arity);
297 while (++l < right) {
298 if (cmp_(heap_[l], heap_[c])) {
299 c = l;
300 }
301 }
302
303 // Current item has lower or equal priority than the child with
304 // minimum priority, stop.
305 if (!cmp_(heap_[c], value)) {
306 break;
307 }
308
309 // Swap current item with the child with minimum priority.
310 heap_[k] = std::move(heap_[c]);
311 handles_[heap_[k]] = k;
312 k = c;
313 }
314 handles_[value] = k;
315 heap_[k] = std::move(value);
316 }
317
318 //! Reorganize heap_ into a heap.
319 void heapify() {
320 key_type max_key = heap_.empty() ? 0 : heap_.front();
321 if (heap_.size() >= 2) {
322 // Iterate from the last internal node up to the root.
323 size_t last_internal = (heap_.size() - 2) / arity;
324 for (size_t i = last_internal + 1; i; --i) {
325 // Index of the current internal node.
326 size_t cur = i - 1;
327 key_type value = std::move(heap_[cur]);
328 max_key = std::max(max_key, value);
329
330 do {
331 size_t l = left(cur);
332 max_key = std::max(max_key, heap_[l]);
333 // Find the minimum child of cur.
334 size_t min_elem = l;
335 for (size_t j = l + 1;
336 j - l < arity && j < heap_.size(); ++j) {
337 if (cmp_(heap_[j], heap_[min_elem]))
338 min_elem = j;
339 max_key = std::max(max_key, heap_[j]);
340 }
341
342 // One of the children of cur is less then cur: swap and
343 // do another iteration.
344 if (cmp_(heap_[min_elem], value)) {
345 heap_[cur] = std::move(heap_[min_elem]);
346 cur = min_elem;
347 }
348 else
349 break;
350 } while (cur <= last_internal);
351 heap_[cur] = std::move(value);
352 }
353 }
354 // initialize handles_ vector
355 handles_.resize(std::max(handles_.size(), static_cast<size_t>(max_key) + 1), not_present());
356 for (size_t i = 0; i < heap_.size(); ++i)
357 handles_[heap_[i]] = i;
358 }
359};
360
361//! make template alias due to similarity with std::priority_queue
362template <typename KeyType, unsigned Arity = 2,
363 typename Compare = std::less<KeyType> >
366
367//! \}
368
369} // namespace tlx
370
371#endif // !TLX_CONTAINER_D_ARY_ADDRESSABLE_INT_HEAP_HEADER
372
373/******************************************************************************/
This class implements an addressable integer priority queue, precisely a d-ary heap.
void build_heap(std::vector< key_type > &&keys)
Builds a heap from the vector keys. Items of keys are moved.
static constexpr key_type not_present()
Marks a key that is not in the heap.
DAryAddressableIntHeap(compare_type cmp=compare_type())
Allocates an empty heap.
DAryAddressableIntHeap(const DAryAddressableIntHeap &)=default
Copy.
bool sanity_check()
For debugging: runs a BFS from the root node and verifies that the heap property is respected.
size_t capacity() const noexcept
Returns the capacity of the heap.
void sift_up(size_t k)
Pushes the node at position k up until either it becomes the root or its parent has lower or equal pr...
size_t parent(size_t k) const
Returns the position of the parent of the node at position k.
size_t size() const noexcept
Returns the number of items in the heap.
bool empty() const noexcept
Returns true if the heap has no items, false otherwise.
key_type extract_top()
Removes and returns the top item.
void build_heap(const std::vector< key_type > &keys)
Builds a heap from the vector keys. Items of keys are copied.
void build_heap(InputIterator first, InputIterator last)
Builds a heap from a container.
void remove(key_type key)
Removes the item with key key.
void reserve(size_t new_size)
Allocates space for new_size items.
size_t left(size_t k) const
Returns the position of the left child of the node at position k.
void heapify()
Reorganize heap_ into a heap.
DAryAddressableIntHeap(DAryAddressableIntHeap &&)=default
Move.
void update(key_type key)
Updates the priority queue after the priority associated to the item with key key has been changed; i...
bool contains(key_type key) const
Returns true if the key key is in the heap, false otherwise.
void push(key_type &&new_key)
Inserts a new item.
void push(const key_type &new_key)
Inserts a new item.
const key_type & top() const noexcept
Returns the top item.
DAryAddressableIntHeap & operator=(const DAryAddressableIntHeap &)=default
void sift_down(size_t k)
Pushes the item at position k down until either it becomes a leaf or all its children have higher pri...
DAryAddressableIntHeap< KeyType, Arity, Compare > d_ary_addressable_int_heap
make template alias due to similarity with std::priority_queue