1 namespace MappingBinaryHeap{
 2 /*
 3     DS:
 4         Datastructure to show the value
 5     Heap:
 6         1.Ds:value
 7         2.idx:index
 8     pos:
 9         The position for each index
10     len:
11         The volum n of heap
12     hh:
13         heap
14     Push:
15         insert an element
16     Pop:
17         pop an element:
18             1.pop(pos[]) pop the element index
19             2.pop(1) pop the 'max' one
20 */
21     struct DS{
22         int next;
23         DS(){}
24         DS(int x) : next(x){}
25         bool operator <(const DS &A) const {
26             if (next == -1)
27                 return true;
28             if (A.next == -1)
29                 return false;
30             return next > A.next;
31         }
32         void init() {
33             next = 0;
34         }
35     };
36     #define maxn N
37     struct Heap {
38         int idx;
39         DS val;
40     }hh[maxn];
41     int pos[maxn];
42     int len;
43     bool Prior(Heap a, Heap b) {
44         return a.val < b.val;
45     }
46     void Push(Heap s) {
47         int i;
48         for (i = ++len; i > 1 && Prior(s, hh[i / 2]); i /= 2) {
49             hh[i] = hh[i / 2];
50             pos[hh[i].idx] = i;
51         }
52         hh[i] = s;
53         pos[hh[i].idx] = i;
54     }
55     Heap Pop(int idx) {
56         if (idx == -1)
57             return hh[0];
58         Heap ret = hh[idx];
59         Heap last = hh[len--];
60         int i, s;
61         for (i = idx; i * 2 <= len; i = s) {
62             s = i * 2;
63             if (s + 1 <= len && Prior(hh[s + 1], hh[s])) {
64                 s++;
65             }
66             if (Prior(hh[s], last)) {
67                 hh[i] = hh[s];
68                 pos[hh[i].idx] = i;
69             } else {
70                 break;
71             }
72         }
73         hh[i] = last;
74         pos[hh[i].idx] = i;
75         for (i = idx; i > 1 && Prior(hh[i], hh[i / 2]); i /= 2) {
76             Heap buf = hh[i];
77             hh[i] = hh[i / 2];
78             hh[i / 2] = buf;
79             pos[hh[i].idx] = i;
80             pos[hh[i / 2].idx] = i / 2;
81         }
82         return ret;
83     }
84     void init() {
85         hh[0].val.init();
86         len = 0;
87     }
88 };
89 /*
90     映射二叉堆  MappingBinaryHeap
91 */