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  for (typename std::vector<Type>::iterator it = c_.begin();
82  it < c_.end(); ++it)
83  {
84  if (!std::forward<Functor>(f)(*it)) continue;
85  std::swap(*it, c_.back());
86  sift_down(c_.begin(), c_.end(), cmp_, c_.size() - 1, it);
87  c_.pop_back();
88  }
89  return result;
90  }
91 
92  //! \}
93 
94  //! \name Free Binary Heap Methods
95  //! \{
96 
97  template <typename Iterator>
98  static void sift_up(Iterator first, Iterator last,
99  const Compare& comp, difference_type len) {
100  if (len > 1)
101  {
102  len = (len - 2) / 2;
103  Iterator ptr = first + len;
104  if (comp(*ptr, *(--last)))
105  {
106  value_type t = std::move(*last);
107  do
108  {
109  *last = std::move(*ptr);
110  last = ptr;
111  if (len == 0)
112  break;
113  len = (len - 1) / 2;
114  ptr = first + len;
115  } while (comp(*ptr, t));
116  *last = std::move(t);
117  }
118  }
119  }
120 
121  template <typename Iterator>
122  static void push_heap(Iterator first, Iterator last, const Compare& comp) {
123  sift_up(first, last, comp, last - first);
124  }
125 
126  template <typename Iterator>
127  static void sift_down(
128  Iterator first, Iterator /* last */,
129  const Compare& comp, difference_type len, Iterator start) {
130  // left-child of start is at 2 * start + 1
131  // right-child of start is at 2 * start + 2
132  difference_type child = start - first;
133 
134  if (len < 2 || (len - 2) / 2 < child)
135  return;
136 
137  child = 2 * child + 1;
138  Iterator child_i = first + child;
139 
140  if ((child + 1) < len && comp(*child_i, *(child_i + 1))) {
141  // right-child exists and is greater than left-child
142  ++child_i, ++child;
143  }
144 
145  // check if we are in heap-order
146  if (comp(*child_i, *start))
147  // we are, start is larger than it's largest child
148  return;
149 
150  value_type top = std::move(*start);
151  do {
152  // we are not in heap-order, swap the parent with it's largest child
153  *start = std::move(*child_i);
154  start = child_i;
155 
156  if ((len - 2) / 2 < child)
157  break;
158 
159  // recompute the child based off of the updated parent
160  child = 2 * child + 1;
161  child_i = first + child;
162 
163  if ((child + 1) < len && comp(*child_i, *(child_i + 1))) {
164  // right-child exists and is greater than left-child
165  ++child_i, ++child;
166  }
167  // check if we are in heap-order
168  } while (!comp(*child_i, top));
169  *start = std::move(top);
170  }
171 
172  template <typename Iterator>
173  static void pop_heap(Iterator first, Iterator last,
174  const Compare& comp, difference_type len) {
175  if (len > 1)
176  {
177  std::swap(*first, *(--last));
178  sift_down(first, last, comp, len - 1, first);
179  }
180  }
181 
182  template <typename Iterator>
183  static void pop_heap(Iterator first, Iterator last, const Compare& comp) {
184  pop_heap(first, last, comp, last - first);
185  }
186 
187  //! \}
188 
189 private:
190  //! array holding binary heap
192 
193  //! compare
194  Compare cmp_;
195 };
196 
197 } // namespace common
198 } // namespace thrill
199 
200 #endif // !THRILL_COMMON_BINARY_HEAP_HEADER
201 
202 /******************************************************************************/
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)
Definition: binary_heap.hpp:98
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