Thrill  0.1
d_ary_heap.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/container/d_ary_heap.hpp
3  *
4  * Part of tlx - http://panthema.net/tlx
5  *
6  * Copyright (C) 2019 Eugenio Angriman <[email protected]>
7  * Copyright (C) 2019 Timo Bingmann <[email protected]>
8  *
9  * All rights reserved. Published under the Boost Software License, Version 1.0
10  ******************************************************************************/
11 
12 #ifndef TLX_CONTAINER_D_ARY_HEAP_HEADER
13 #define TLX_CONTAINER_D_ARY_HEAP_HEADER
14 
15 #include <cassert>
16 #include <cstddef>
17 #include <functional>
18 #include <limits>
19 #include <queue>
20 #include <vector>
21 
22 namespace tlx {
23 
24 //! \addtogroup tlx_container
25 //! \{
26 
27 /*!
28  * This class implements a d-ary comparison-based heap usable as a priority
29  * queue. Higher arity yields better cache efficiency.
30  *
31  * \tparam KeyType Key type.
32  * \tparam Arity A positive integer.
33  * \tparam Compare Function object to order keys.
34  */
35 template <typename KeyType, unsigned Arity = 2,
36  typename Compare = std::less<KeyType> >
37 class DAryHeap
38 {
39  static_assert(Arity, "Arity must be greater than zero.");
40 
41 public:
42  using key_type = KeyType;
43  using compare_type = Compare;
44 
45  static constexpr size_t arity = Arity;
46 
47 protected:
48  //! Cells in the heap.
49  std::vector<key_type> heap_;
50 
51  //! Compare function.
53 
54 public:
55  //! Allocates an empty heap.
57  : heap_(0), cmp_(cmp) { }
58 
59  //! Allocates space for \c new_size items.
60  void reserve(size_t new_size) {
61  heap_.reserve(new_size);
62  }
63 
64  //! Copy.
65  DAryHeap(const DAryHeap&) = default;
66  DAryHeap& operator = (const DAryHeap&) = default;
67 
68  //! Move.
69  DAryHeap(DAryHeap&&) = default;
70  DAryHeap& operator = (DAryHeap&&) = default;
71 
72  //! Empties the heap.
73  void clear() {
74  heap_.clear();
75  }
76 
77  //! Returns the number of items in the heap.
78  size_t size() const noexcept { return heap_.size(); }
79 
80  //! Returns the capacity of the heap.
81  size_t capacity() const noexcept { return heap_.capacity(); }
82 
83  //! Returns true if the heap has no items, false otherwise.
84  bool empty() const noexcept { return heap_.empty(); }
85 
86  //! Inserts a new item.
87  void push(const key_type& new_key) {
88  // Insert the new item at the end of the heap.
89  heap_.push_back(new_key);
90  sift_up(heap_.size() - 1);
91  }
92 
93  //! Inserts a new item.
94  void push(key_type&& new_key) {
95  // Insert the new item at the end of the heap.
96  heap_.push_back(std::move(new_key));
97  sift_up(heap_.size() - 1);
98  }
99 
100  //! Returns the top item.
101  const key_type& top() const noexcept {
102  assert(!empty());
103  return heap_[0];
104  }
105 
106  //! Removes the top item.
107  void pop() {
108  assert(!empty());
109  std::swap(heap_[0], heap_.back());
110  heap_.pop_back();
111  if (!heap_.empty())
112  sift_down(0);
113  }
114 
115  //! Removes and returns the top item.
117  key_type top_item = top();
118  pop();
119  return top_item;
120  }
121 
122  //! Rebuilds the heap.
123  void update_all() {
124  heapify();
125  }
126 
127  //! Builds a heap from a container.
128  template <class InputIterator>
129  void build_heap(InputIterator first, InputIterator last) {
130  heap_.assign(first, last);
131  heapify();
132  }
133 
134  //! Builds a heap from the vector \c keys. Items of \c keys are copied.
135  void build_heap(const std::vector<key_type>& keys) {
136  heap_.resize(keys.size());
137  std::copy(keys.begin(), keys.end(), heap_.begin());
138  heapify();
139  }
140 
141  //! Builds a heap from the vector \c keys. Items of \c keys are moved.
142  void build_heap(std::vector<key_type>&& keys) {
143  if (!empty())
144  heap_.clear();
145  heap_ = std::move(keys);
146  heapify();
147  }
148 
149  //! For debugging: runs a BFS from the root node and verifies that the heap
150  //! property is respected.
151  bool sanity_check() {
152  if (empty()) {
153  return true;
154  }
155  std::queue<size_t> q;
156  // Explore from the root.
157  q.push(0);
158  while (!q.empty()) {
159  size_t s = q.front();
160  q.pop();
161  size_t l = left(s);
162  for (size_t i = 0; i < arity && l < heap_.size(); ++i) {
163  // Check that the priority of the children is not strictly less
164  // than their parent.
165  if (cmp_(heap_[l], heap_[s]))
166  return false;
167  q.push(l++);
168  }
169  }
170  return true;
171  }
172 
173 private:
174  //! Returns the position of the left child of the node at position \c k.
175  size_t left(size_t k) const { return arity * k + 1; }
176 
177  //! Returns the position of the parent of the node at position \c k.
178  size_t parent(size_t k) const { return (k - 1) / arity; }
179 
180  //! Pushes the node at position \c k up until either it becomes the root or
181  //! its parent has lower or equal priority.
182  void sift_up(size_t k) {
183  key_type value = std::move(heap_[k]);
184  size_t p = parent(k);
185  while (k > 0 && !cmp_(heap_[p], value)) {
186  heap_[k] = std::move(heap_[p]);
187  k = p, p = parent(k);
188  }
189  heap_[k] = std::move(value);
190  }
191 
192  //! Pushes the item at position \c k down until either it becomes a leaf or
193  //! all its children have higher priority
194  void sift_down(size_t k) {
195  key_type value = std::move(heap_[k]);
196  while (true) {
197  size_t l = left(k);
198  if (l >= heap_.size()) {
199  break;
200  }
201  // Get the min child.
202  size_t c = l;
203  size_t right = std::min(heap_.size(), c + arity);
204  while (++l < right) {
205  if (cmp_(heap_[l], heap_[c])) {
206  c = l;
207  }
208  }
209 
210  // Current item has lower or equal priority than the child with
211  // minimum priority, stop.
212  if (!cmp_(heap_[c], value)) {
213  break;
214  }
215 
216  // Swap current item with the child with minimum priority.
217  heap_[k] = std::move(heap_[c]);
218  k = c;
219  }
220  heap_[k] = std::move(value);
221  }
222 
223  //! Reorganize heap_ into a heap.
224  void heapify() {
225  if (heap_.size() >= 2) {
226  // Iterate from the last internal node up to the root.
227  size_t last_internal = (heap_.size() - 2) / arity;
228  for (size_t i = last_internal + 1; i; --i) {
229  // Index of the current internal node.
230  size_t cur = i - 1;
231  key_type value = std::move(heap_[cur]);
232 
233  do {
234  size_t l = left(cur);
235  // Find the minimum child of cur.
236  size_t min_elem = l;
237  for (size_t j = l + 1;
238  j - l < arity && j < heap_.size(); ++j) {
239  if (cmp_(heap_[j], heap_[min_elem]))
240  min_elem = j;
241  }
242 
243  // One of the children of cur is less then cur: swap and
244  // do another iteration.
245  if (cmp_(heap_[min_elem], value)) {
246  heap_[cur] = std::move(heap_[min_elem]);
247  cur = min_elem;
248  }
249  else
250  break;
251  } while (cur <= last_internal);
252  heap_[cur] = std::move(value);
253  }
254  }
255  }
256 };
257 
258 //! make template alias due to similarity with std::priority_queue
259 template <typename KeyType, unsigned Arity = 2,
260  typename Compare = std::less<KeyType> >
262 
263 //! \}
264 
265 } // namespace tlx
266 
267 #endif // !TLX_CONTAINER_D_ARY_HEAP_HEADER
268 
269 /******************************************************************************/
bool sanity_check()
Definition: d_ary_heap.hpp:151
void pop()
Removes the top item.
Definition: d_ary_heap.hpp:107
compare_type cmp_
Compare function.
Definition: d_ary_heap.hpp:52
KeyType key_type
Definition: d_ary_heap.hpp:42
void push(const key_type &new_key)
Inserts a new item.
Definition: d_ary_heap.hpp:87
key_type extract_top()
Removes and returns the top item.
Definition: d_ary_heap.hpp:116
void sift_up(size_t k)
Definition: d_ary_heap.hpp:182
void update_all()
Rebuilds the heap.
Definition: d_ary_heap.hpp:123
void sift_down(size_t k)
Definition: d_ary_heap.hpp:194
void clear()
Empties the heap.
Definition: d_ary_heap.hpp:73
This class implements a d-ary comparison-based heap usable as a priority queue.
Definition: d_ary_heap.hpp:37
Compare compare_type
Definition: d_ary_heap.hpp:43
size_t parent(size_t k) const
Returns the position of the parent of the node at position k.
Definition: d_ary_heap.hpp:178
size_t left(size_t k) const
Returns the position of the left child of the node at position k.
Definition: d_ary_heap.hpp:175
static constexpr size_t arity
Definition: d_ary_heap.hpp:45
const key_type & top() const noexcept
Returns the top item.
Definition: d_ary_heap.hpp:101
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
void reserve(size_t new_size)
Allocates space for new_size items.
Definition: d_ary_heap.hpp:60
std::vector< key_type > heap_
Cells in the heap.
Definition: d_ary_heap.hpp:49
int value
Definition: gen_data.py:41
bool empty() const noexcept
Returns true if the heap has no items, false otherwise.
Definition: d_ary_heap.hpp:84
DAryHeap(compare_type cmp=compare_type())
Allocates an empty heap.
Definition: d_ary_heap.hpp:56
static uint_pair min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.hpp:217
size_t size() const noexcept
Returns the number of items in the heap.
Definition: d_ary_heap.hpp:78
void build_heap(const std::vector< key_type > &keys)
Builds a heap from the vector keys. Items of keys are copied.
Definition: d_ary_heap.hpp:135
void build_heap(InputIterator first, InputIterator last)
Builds a heap from a container.
Definition: d_ary_heap.hpp:129
DAryHeap & operator=(const DAryHeap &)=default
size_t capacity() const noexcept
Returns the capacity of the heap.
Definition: d_ary_heap.hpp:81
void build_heap(std::vector< key_type > &&keys)
Builds a heap from the vector keys. Items of keys are moved.
Definition: d_ary_heap.hpp:142
void push(key_type &&new_key)
Inserts a new item.
Definition: d_ary_heap.hpp:94
void heapify()
Reorganize heap_ into a heap.
Definition: d_ary_heap.hpp:224