| 284 | typename compare |
| 285 | > |
| 286 | void heapify ( |
| 287 | T& array, |
| 288 | const unsigned long start, |
| 289 | const unsigned long end, |
| 290 | unsigned long i, |
| 291 | const compare& comp |
| 292 | ) |
| 293 | /*! |
| 294 | requires |
| 295 | - T implements operator[] |
| 296 | - the items in array must be comparable by comp |
| 297 | - the items in array must be swappable by a global swap() |
| 298 | - start, end, and i are within the bounds of array |
| 299 | i.e. array[start], array[end], and array[i] are valid elements |
| 300 | - start <= i <= end |
| 301 | - array[i/2] is a max heap |
| 302 | - array[i/2+1] is a max heap |
| 303 | - start and end specify the range of the array we are working with. |
| 304 | ensures |
| 305 | - array[i] is now a max heap |
| 306 | !*/ |
| 307 | { |
| 308 | DLIB_ASSERT (start <= i && i <= end, |
| 309 | "\tvoid heapify()" |
| 310 | << "\n\tstart: " << start |
| 311 | << "\n\tend: " << end |
| 312 | << "\n\ti: " << i ); |
| 313 | |
| 314 | bool keep_going = true; |
| 315 | unsigned long left; |
| 316 | unsigned long right; |
| 317 | unsigned long largest; |
| 318 | while (keep_going) |
| 319 | { |
| 320 | keep_going = false; |
| 321 | left = (i<<1)+1-start; |
| 322 | right = left+1; |
| 323 | |
| 324 | if (left <= end && comp(array[i] , array[left])) |
| 325 | largest = left; |
| 326 | else |
| 327 | largest = i; |
| 328 | |
| 329 | if (right <= end && comp(array[largest] , array[right])) |
| 330 | largest = right; |
| 331 | |
| 332 | if (largest != i) |
| 333 | { |
| 334 | exchange(array[i],array[largest]); |
| 335 | i = largest; |
| 336 | keep_going = true; |
| 337 | } |
| 338 | } |
| 339 | } |
| 340 | |
| 341 | // ---------------------------------------------------------------------------------------- |
| 342 | } |
no test coverage detected