MCPcopy Create free account
hub / github.com/davisking/dlib / heapify

Function heapify

dlib/sort.h:286–339  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

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 }

Callers 1

hsort_arrayFunction · 0.85

Calls 2

compFunction · 0.85
exchangeFunction · 0.85

Tested by

no test coverage detected