equal
deleted
inserted
replaced
101 BinHeap(KeyIntMap &_kim) : kim(_kim) {} |
101 BinHeap(KeyIntMap &_kim) : kim(_kim) {} |
102 BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {} |
102 BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {} |
103 |
103 |
104 |
104 |
105 int size() const { return data.size(); } |
105 int size() const { return data.size(); } |
106 bool empty() const { return size() == 0; } |
106 bool empty() const { return data.empty(); } |
107 |
107 |
108 private: |
108 private: |
109 static int parent(int i) { return (i-1)/2; } |
109 static int parent(int i) { return (i-1)/2; } |
110 static int second_child(int i) { return 2*i+2; } |
110 static int second_child(int i) { return 2*i+2; } |
111 bool less(const PairType &p1, const PairType &p2) { |
111 bool less(const PairType &p1, const PairType &p2) { |
118 void move(const PairType &p, int i) { |
118 void move(const PairType &p, int i) { |
119 data[i] = p; |
119 data[i] = p; |
120 kim.put(p.first, i); |
120 kim.put(p.first, i); |
121 } |
121 } |
122 |
122 |
|
123 void rmidx(int h) { |
|
124 int n = data.size()-1; |
|
125 if( h>=0 && h<=n ) { |
|
126 kim.put(data[h].first, POST_HEAP); |
|
127 if ( h<n ) { |
|
128 bubble_down(h, data[n], n); |
|
129 } |
|
130 data.pop_back(); |
|
131 } |
|
132 } |
|
133 |
123 public: |
134 public: |
124 void push(const PairType &p) { |
135 void push(const PairType &p) { |
125 int n = data.size(); |
136 int n = data.size(); |
126 data.resize(n+1); |
137 data.resize(n+1); |
127 bubble_up(n, p); |
138 bubble_up(n, p); |
136 // FIXME: test size>0 ? |
147 // FIXME: test size>0 ? |
137 return data[0].second; |
148 return data[0].second; |
138 } |
149 } |
139 |
150 |
140 void pop() { |
151 void pop() { |
141 int n = data.size()-1; |
152 rmidx(0); |
142 if( n>=0 ) { |
153 } |
143 kim.put(data[0].first, POST_HEAP); |
154 |
144 if ( n>0 ) { |
155 void erase(const Key &k) { |
145 bubble_down(0, data[n], n); |
156 rmidx(kim.get(k)); |
146 } |
|
147 data.pop_back(); |
|
148 } |
|
149 } |
157 } |
150 |
158 |
151 const Val get(const Key &k) const { |
159 const Val get(const Key &k) const { |
152 int idx = kim.get(k); |
160 int idx = kim.get(k); |
153 return data[idx].second; |
161 return data[idx].second; |