prototype/priority-queue.h at main · maierlars/prototype · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#ifndef PROTOTYPE_PRIORITY_QUEUE_H
#define PROTOTYPE_PRIORITY_QUEUE_H

#include <algorithm>
#include <vector>

namespace foobar {

template<typename T>
class priority_queue {
 public:
  [[nodiscard]] auto find_max() -> T const&;

  [[nodiscard]] auto extract_max() -> T;

  template<typename... Args>
  auto emplace(Args&&... args) -> void;

  [[nodiscard]] auto empty() const -> bool;

 private:
  std::vector<T> _heap;
};

template<typename T>
auto priority_queue<T>::empty() const -> bool {
  return _heap.empty();
}

template<typename T>
template<typename... Args>
auto priority_queue<T>::emplace(Args &&... args) -> void {
  _heap.emplace_back(std::forward<Args>(args)...);
  std::push_heap(_heap.begin(), _heap.end());
}

template<typename T>
auto priority_queue<T>::find_max() -> T const & {
  return _heap.front();
}

template<typename T>
auto priority_queue<T>::extract_max() -> T {
  std::pop_heap(_heap.begin(), _heap.end());
  auto value = std::move(_heap.back());
  _heap.pop_back();

  return value;
}

}

#endif  // PROTOTYPE_PRIORITY_QUEUE_H