Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
binary_heap.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * thrill/common/binary_heap.hpp
3  *
4  * A simple binary heap priority queue, except that one can additionally find
5  * and delete arbitrary items in O(n).
6  *
7  * The standard binary heap implementation methods were copied from libc++ under
8  * the MIT license.
9  *
10  * Part of Project Thrill - http://project-thrill.org
11  *
12  * Copyright (C) 2016 Timo Bingmann <[email protected]>
13  *
14  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
15  ******************************************************************************/
16 
17 #pragma once
18 #ifndef THRILL_COMMON_BINARY_HEAP_HEADER
19 #define THRILL_COMMON_BINARY_HEAP_HEADER
20 
21 #include <algorithm>
22 #include <functional>
23 #include <vector>
24 
25 namespace thrill {
26 namespace common {
27 
28 //! A simple binary heap priority queue, except that one can additionally find
29 //! and delete arbitrary items in O(n).
30 template <typename Type, typename Compare = std::less<Type> >
32 {
33 public:
34  using Container = std::vector<Type>;
35  using value_type = Type;
36  using const_reference = const Type&;
37  using size_type = size_t;
38  using difference_type = typename Container::difference_type;
39 
40  //! \name PQ Interface
41  //! \{
42 
43  explicit BinaryHeap(const Compare& cmp = Compare())
44  : cmp_(cmp) { }
45 
46  //! check if PQ is empty
47  bool empty() const { return c_.empty(); }
48 
49  //! return number of items in the PQ
50  size_type size() const { return c_.size(); }
51 
52  //! return reference to top item in PQ
53  const_reference top() const { return c_.front(); }
54 
55  //! add an items in the PQ.
56  template <typename... Args>
57  void emplace(Args&& ... args) {
58  c_.emplace_back(std::forward<Args>(args) ...);
59  push_heap(c_.begin(), c_.end(), cmp_);
60  }
61 
62  //! remove the top item in the PQ
63  void pop() {
64  pop_heap(c_.begin(), c_.end(), cmp_);
65  c_.pop_back();
66  }
67 
68  //! \}
69 
70  //! \name Additional Methods
71  //! \{
72 
73  //! direct access to heap container
74  Container& container() { return c_; }
75 
76  //! iterate over all items, delete those for which f returns true. Takes
77  //! time O(n). If you need to erase items frequently, use a different PQ.
78  template <typename Functor>
79  size_t erase(Functor&& f) {
80  size_t result = 0;
81  size_t i = 0;
82  while (i != c_.size()) {
83  if (!std::forward<Functor>(f)(c_[i])) {
84  ++i;
85  }
86  else {
87  std::swap(c_[i], c_.back());
88  sift_down(c_.begin(), c_.end(), cmp_, c_.size() - 1,
89  c_.begin() + i);
90  c_.pop_back();
91  // recheck i
92  }
93  }
94  return result;
95  }
96 
97  //! \}
98 
99  //! \name Free Binary Heap Methods
100  //! \{
101 
102  template <typename Iterator>
103  static void sift_up(Iterator first, Iterator last,
104  const Compare& comp, difference_type len) {
105  if (len > 1)
106  {
107  len = (len - 2) / 2;
108  Iterator ptr = first + len;
109  if (comp(*ptr, *(--last)))
110  {
111  value_type t = std::move(*last);
112  do
113  {
114  *last = std::move(*ptr);
115  last = ptr;
116  if (len == 0)
117  break;
118  len = (len - 1) / 2;
119  ptr = first + len;
120  } while (comp(*ptr, t));
121  *last = std::move(t);
122  }
123  }
124  }
125 
126  template <typename Iterator>
127  static void push_heap(Iterator first, Iterator last, const Compare& comp) {
128  sift_up(first, last, comp, last - first);
129  }
130 
131  template <typename Iterator>
132  static void sift_down(
133  Iterator first, Iterator /* last */,
134  const Compare& comp, difference_type len, Iterator start) {
135  // left-child of start is at 2 * start + 1
136  // right-child of start is at 2 * start + 2
137  difference_type child = start - first;
138 
139  if (len < 2 || (len - 2) / 2 < child)
140  return;
141 
142  child = 2 * child + 1;
143  Iterator child_i = first + child;
144 
145  if ((child + 1) < len && comp(*child_i, *(child_i + 1))) {
146  // right-child exists and is greater than left-child
147  ++child_i, ++child;
148  }
149 
150  // check if we are in heap-order
151  if (comp(*child_i, *start))
152  // we are, start is larger than it's largest child
153  return;
154 
155  value_type top = std::move(*start);
156  do {
157  // we are not in heap-order, swap the parent with it's largest child
158  *start = std::move(*child_i);
159  start = child_i;
160 
161  if ((len - 2) / 2 < child)
162  break;
163 
164  // recompute the child based off of the updated parent
165  child = 2 * child + 1;
166  child_i = first + child;
167 
168  if ((child + 1) < len && comp(*child_i, *(child_i + 1))) {
169  // right-child exists and is greater than left-child
170  ++child_i, ++child;
171  }
172  // check if we are in heap-order
173  } while (!comp(*child_i, top));
174  *start = std::move(top);
175  }
176 
177  template <typename Iterator>
178  static void pop_heap(Iterator first, Iterator last,
179  const Compare& comp, difference_type len) {
180  if (len > 1)
181  {
182  std::swap(*first, *(--last));
183  sift_down(first, last, comp, len - 1, first);
184  }
185  }
186 
187  template <typename Iterator>
188  static void pop_heap(Iterator first, Iterator last, const Compare& comp) {
189  pop_heap(first, last, comp, last - first);
190  }
191 
192  //! \}
193 
194 private:
195  //! array holding binary heap
197 
198  //! compare
199  Compare cmp_;
200 };
201 
202 } // namespace common
203 } // namespace thrill
204 
205 #endif // !THRILL_COMMON_BINARY_HEAP_HEADER
206 
207 /******************************************************************************/
void emplace(Args &&...args)
add an items in the PQ.
Definition: binary_heap.hpp:57
typename Container::difference_type difference_type
Definition: binary_heap.hpp:38
Type
VFS object type.
Definition: file_io.hpp:52
static void sift_down(Iterator first, Iterator, const Compare &comp, difference_type len, Iterator start)
void pop()
remove the top item in the PQ
Definition: binary_heap.hpp:63
Container c_
array holding binary heap
static void sift_up(Iterator first, Iterator last, const Compare &comp, difference_type len)
static void push_heap(Iterator first, Iterator last, const Compare &comp)
bool empty() const
check if PQ is empty
Definition: binary_heap.hpp:47
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
static void pop_heap(Iterator first, Iterator last, const Compare &comp)
const_reference top() const
return reference to top item in PQ
Definition: binary_heap.hpp:53
Container & container()
direct access to heap container
Definition: binary_heap.hpp:74
size_t erase(Functor &&f)
Definition: binary_heap.hpp:79
size_type size() const
return number of items in the PQ
Definition: binary_heap.hpp:50
static void pop_heap(Iterator first, Iterator last, const Compare &comp, difference_type len)
BinaryHeap(const Compare &cmp=Compare())
Definition: binary_heap.hpp:43