min heap

ソースコード

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

仕様

Warning

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