ConicBundle
heapsort.hxx
Go to the documentation of this file.
1 
2 
3 #ifndef CH_TOOLS__HEAPSORT_HXX
4 #define CH_TOOLS__HEAPSORT_HXX
5 
14 #include "mymath.hxx"
15 
16 namespace CH_Tools {
17 
40 
48  template<class I,class V> void heapify(int i, int n, I& ind,const V& val,bool non_decreasing=true);
49 
56  template<class I,class V> void build_heap(int n, I& ind, const V& val,bool non_decreasing=true);
57 
65  template<class I,class V> void heapsort(int n, I& ind, const V& val,bool non_decreasing=true);
66 
74  template<class I,class V> void heapify(int i, int n, I* ind,const V* val,bool non_decreasing=true);
75 
82  template<class I,class V> void build_heap(int n, I* ind, const V* val,bool non_decreasing=true);
83 
90  template<class I,class V> void heapsort(int n, I* ind, const V* val,bool non_decreasing=true);
91 
92 
94 
95 //--------------------------------------------------------------
96 // heapsort -- implementation
97 //--------------------------------------------------------------
98 
99 
100  template<class I,class V> inline void heapify(int i,int n,I& ind,const V& val,bool non_decreasing)
101 {
102  int k,j;
103  k=i;
104  if (non_decreasing){
105  while(2*k+1<n){
106  using namespace CH_Matrix_Classes;
107  if (2*k==n-2){
108  if (val[ind[k]]<val[ind[2*k+1]])
109  swap(ind[k],ind[2*k+1]);
110  break;
111  }
112  if ((val[ind[k]]<val[ind[2*k+1]])||
113  (val[ind[k]]<val[ind[2*k+2]])){
114  if (val[ind[2*k+1]]>val[ind[2*k+2]]) j=2*k+1;
115  else j=2*k+2;
116  swap(ind[k],ind[j]);
117  k=j;
118  }
119  else break;
120  }
121  }
122  else {
123  while(2*k+1<n){
124  using namespace CH_Matrix_Classes;
125  if (2*k==n-2){
126  if (val[ind[k]]>val[ind[2*k+1]])
127  swap(ind[k],ind[2*k+1]);
128  break;
129  }
130  if ((val[ind[k]]>val[ind[2*k+1]])||
131  (val[ind[k]]>val[ind[2*k+2]])){
132  if (val[ind[2*k+1]]<val[ind[2*k+2]]) j=2*k+1;
133  else j=2*k+2;
134  swap(ind[k],ind[j]);
135  k=j;
136  }
137  else break;
138  }
139  }
140 }
141 
142  template<class I,class V> inline void build_heap(int n,I& ind,const V& val,bool non_decreasing)
143 {
144  for(int i=n/2;--i>=0;) heapify(i,n,ind,val,non_decreasing);
145 }
146 
147  template<class I,class V> inline void heapsort(int n,I& ind,const V& val,bool non_decreasing)
148 {
149  int i;
150 
151  //build heap
152  build_heap(n,ind,val,non_decreasing);
153 
154  //extract greatest and rebuild heap
155  for(i=n;--i>=1;){
156  using namespace CH_Matrix_Classes;
157  swap(ind[i],ind[0]);
158  heapify(0,i,ind,val,non_decreasing);
159  }
160 }
161 
162  template<class I,class V> inline void heapify(int i,int n,I* ind,const V* val,bool non_decreasing)
163 {
164  I indi=ind[i];
165  V valindi=val[indi];
166  if (non_decreasing){
167  int j=2*i+1;
168  while(j<n){
169  using namespace CH_Matrix_Classes;
170  if (j==n-1){
171  if (valindi<val[ind[j]]){
172  ind[i]=ind[j];
173  i=j;
174  }
175  break;
176  }
177  V v1=val[ind[j]];
178  V v2=val[ind[j+1]];
179  if (v1<v2) {
180  if (valindi<v2){
181  j++;
182  ind[i]=ind[j];
183  i=j;
184  }
185  else {
186  break;
187  }
188  }
189  else {
190  if (valindi<v1){
191  ind[i]=ind[j];
192  i=j;
193  }
194  else {
195  break;
196  }
197  }
198  j=2*i+1;
199  }
200  ind[i]=indi;
201  }
202  else {
203  int j=2*i+1;
204  while(j<n){
205  using namespace CH_Matrix_Classes;
206  if (j==n-1){
207  if (valindi>val[ind[j]]){
208  ind[i]=ind[j];
209  i=j;
210  }
211  break;
212  }
213  V v1=val[ind[j]];
214  V v2=val[ind[j+1]];
215  if (v1>v2) {
216  if (valindi>v2){
217  j++;
218  ind[i]=ind[j];
219  i=j;
220  }
221  else {
222  break;
223  }
224  }
225  else {
226  if (valindi>v1){
227  ind[i]=ind[j];
228  i=j;
229  }
230  else {
231  break;
232  }
233  }
234  j=2*i+1;
235  }
236  ind[i]=indi;
237  }
238 }
239 
240  template<class I,class V> inline void build_heap(int n,I* ind,const V* val,bool non_decreasing)
241 {
242  for(int i=n/2;--i>=0;) heapify(i,n,ind,val,non_decreasing);
243 }
244 
245  template<class I,class V> inline void heapsort(int n,I* ind,const V* val,bool non_decreasing)
246 {
247  int i;
248 
249  //build heap
250  build_heap(n,ind,val,non_decreasing);
251 
252  //extract greatest and rebuild heap
253  for(i=n;--i>=1;){
254  using namespace CH_Matrix_Classes;
255  swap(ind[i],ind[0]);
256  heapify(0,i,ind,val,non_decreasing);
257  }
258 }
259 
260 
261 
262 }
263 
264 #endif
265 
CH_Tools
Some convenient inline tools like a clock for timing, a random number generator, a heapsort template ...
Definition: clock.hxx:29
CH_Tools::build_heap
void build_heap(int n, I &ind, const V &val, bool non_decreasing=true)
Build a heap out of ind[0] to ind[n-1], so that val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for ...
Definition: heapsort.hxx:142
CH_Matrix_Classes::swap
void swap(double &a, double &b)
swaps two double variables
Definition: mymath.hxx:79
CH_Tools::heapsort
void heapsort(int n, I &ind, const V &val, bool non_decreasing=true)
Sort ind[0]...ind[n-1] so that val[ind[i]]<=val[ind[j]] for 0<=i<j<n.
Definition: heapsort.hxx:147
mymath.hxx
Header defining simple functions like max, min, abs.
CH_Matrix_Classes
Matrix Classes and Linear Algebra. See Matrix Classes (namespace CH_Matrix_Classes) for a quick intro...
Definition: PSCOracle.hxx:20
CH_Tools::heapify
void heapify(int i, int n, I &ind, const V &val, bool non_decreasing=true)
Heapify element i (in 0,...,n-1) in ind, so that afterwards val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for the subtree with root i.
Definition: heapsort.hxx:100
Generated by   doxygen 1.8.13