tlx
Loading...
Searching...
No Matches
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 <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_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
22namespace 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 */
35template <typename KeyType, unsigned Arity = 2,
36 typename Compare = std::less<KeyType> >
38{
39 static_assert(Arity, "Arity must be greater than zero.");
40
41public:
42 using key_type = KeyType;
43 using compare_type = Compare;
44
45 static constexpr size_t arity = Arity;
46
47protected:
48 //! Cells in the heap.
49 std::vector<key_type> heap_;
50
51 //! Compare function.
53
54public:
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;
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.
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
173private:
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
259template <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/******************************************************************************/
This class implements a d-ary comparison-based heap usable as a priority queue.
DAryHeap(DAryHeap &&)=default
Move.
void build_heap(std::vector< key_type > &&keys)
Builds a heap from the vector keys. Items of keys are moved.
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 pop()
Removes the top item.
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.
Compare compare_type
void build_heap(const std::vector< key_type > &keys)
Builds a heap from the vector keys. Items of keys are copied.
KeyType key_type
void build_heap(InputIterator first, InputIterator last)
Builds a heap from a container.
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 update_all()
Rebuilds the heap.
void heapify()
Reorganize heap_ into a heap.
DAryHeap & operator=(const DAryHeap &)=default
DAryHeap(const DAryHeap &)=default
Copy.
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.
void clear()
Empties the heap.
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...
DAryHeap(compare_type cmp=compare_type())
Allocates an empty heap.
DAryHeap< KeyType, Arity, Compare > d_ary_heap
make template alias due to similarity with std::priority_queue