| 5 | bool operator ()(const int &a, const int &b) const { |
| 6 | return a < b; } }; |
| 7 | template <class Compare = default_int_cmp> struct heap { |
| 8 | int len, count, *q, *loc, tmp; |
| 9 | Compare _cmp; |
| 10 | inline bool cmp(int i, int j) { return _cmp(q[i], q[j]); } |
| 11 | inline void swp(int i, int j) { |
| 12 | SWP(q[i], q[j]), SWP(loc[q[i]], loc[q[j]]); } |
| 13 | void swim(int i) { |
| 14 | while (i > 0) { |
| 15 | int p = (i - 1) / 2; |
| 16 | if (!cmp(i, p)) break; |
| 17 | swp(i, p), i = p; } } |
| 18 | void sink(int i) { |
| 19 | while (true) { |
| 20 | int l = 2*i + 1, r = l + 1; |
| 21 | if (l >= count) break; |
| 22 | int m = r >= count || cmp(l, r) ? l : r; |
| 23 | if (!cmp(m, i)) break; |
| 24 | swp(m, i), i = m; } } |
| 25 | heap(int init_len = 128) |
| 26 | : count(0), len(init_len), _cmp(Compare()) { |
| 27 | q = new int[len], loc = new int[len]; |
| 28 | memset(loc, 255, len << 2); } |
| 29 | ~heap() { delete[] q; delete[] loc; } |
| 30 | void push(int n, bool fix = true) { |
| 31 | if (len == count || n >= len) { |
| 32 | #ifdef RESIZE |
| 33 | int newlen = 2 * len; |
| 34 | while (n >= newlen) newlen *= 2; |
| 35 | int *newq = new int[newlen], *newloc = new int[newlen]; |
| 36 | rep(i,0,len) newq[i] = q[i], newloc[i] = loc[i]; |
| 37 | memset(newloc + len, 255, (newlen - len) << 2); |
| 38 | delete[] q, delete[] loc; |
| 39 | loc = newloc, q = newq, len = newlen; |
| 40 | #else |
| 41 | assert(false); |
| 42 | #endif |
| 43 | } |
| 44 | assert(loc[n] == -1); |
| 45 | loc[n] = count, q[count++] = n; |
| 46 | if (fix) swim(count-1); } |
| 47 | void pop(bool fix = true) { |
| 48 | assert(count > 0); |
| 49 | loc[q[0]] = -1, q[0] = q[--count], loc[q[0]] = 0; |
| 50 | if (fix) sink(0); |
| 51 | } |
| 52 | int top() { assert(count > 0); return q[0]; } |
| 53 | void heapify() { for (int i = count - 1; i > 0; i--) |
| 54 | if (cmp(i, (i - 1) / 2)) swp(i, (i - 1) / 2); } |
| 55 | void update_key(int n) { |
| 56 | assert(loc[n] != -1), swim(loc[n]), sink(loc[n]); } |
| 57 | bool empty() { return count == 0; } |
| 58 | int size() { return count; } |
| 59 | void clear() { count = 0, memset(loc, 255, len << 2); }}; |
| 60 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no outgoing calls
no test coverage detected