max heap

ソースコード

  1#include <iostream>
  2#include <vector>
  3using namespace std;
  4
  5// MaxHeap
  6namespace titan23 {
  7
  8    template<typename T>
  9    class MaxHeap {
 10      public:
 11        vector<T> a;
 12
 13      private:
 14        void _heapify() {
 15            for (int i = (int)a.size(); i >= 0; --i) {
 16                _down(i);
 17            }
 18        }
 19
 20        void _down(int i) {
 21            int n = a.size();
 22            while (i<<1|1 < n) {
 23                int u = i*2+1, v = i*2+2;
 24                if (v < n && a[u] < a[v]) u = v;
 25                if (a[i] < a[u]) {
 26                    swap(a[i], a[u]);
 27                    i = u;
 28                } else {
 29                    break;
 30                }
 31            }
 32        }
 33
 34        void _up(int i) {
 35            while (i > 0) {
 36                int p = (i - 1) >> 1;
 37                if (a[i] > a[p]) {
 38                    swap(a[i], a[p]);
 39                    i = p;
 40                } else {
 41                    break;
 42                }
 43            }
 44        }
 45
 46      public:
 47        MaxHeap() {}
 48        MaxHeap(vector<T> a) : a(a) { _heapify(); }
 49
 50        void clear() {
 51            a.clear();
 52        }
 53
 54        //! 最大の要素を返す / `O(1)`
 55        T get_max() const {
 56            return a[0];
 57        }
 58
 59        //! 最大の要素を削除して返す / `O(logn)`
 60        T pop_max() {
 61            T res = a[0];
 62            a[0] = a.back();
 63            a.pop_back();
 64            _down(0);
 65            return res;
 66        }
 67
 68        //! `key` を追加する / `O(logn)`
 69        void push(const T key) {
 70            a.emplace_back(key);
 71            _up(a.size() - 1);
 72        }
 73
 74        //! `push` して `pop` する / `O(logn)`
 75        T pushpoop_max(const T key) {
 76            if (a[0] <= key) return key;
 77            T res = a[0];
 78            a[0] = key;
 79            _down(0);
 80            return res;
 81        }
 82
 83        //! 最大の要素を `pop` して返し、新たに `key` を挿入する。 `pop -> push` と同じ / `O(logn)`
 84        T replace_max(const T key) {
 85            T res = a[0];
 86            a[0] = key;
 87            _down(0);
 88            return res;
 89        }
 90
 91        vector<T> tolist() const {
 92            return a;
 93        }
 94
 95        //! 要素数を返す / `O(1)`
 96        int len() const {
 97            return (int)a.size();
 98        }
 99
100        //! 表示する
101        void print() const {
102            vector<T> b = a;
103            sort(b.begin(), b.end());
104            cout << '[';
105            for (int i = 0; i < len()-1; ++i) {
106                cout << b[i] << ", ";
107            }
108            if (!b.empty()) {
109                cout << b.back();
110            }
111            cout << ']' << endl;
112        }
113    };
114} // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/max_heap.cpp