1 // Copyright (C) 2002-2012 Nikolaus Gebhardt
\r
2 // This file is part of the "Irrlicht Engine".
\r
3 // For conditions of distribution and use, see copyright notice in irrlicht.h
\r
5 #ifndef __IRR_HEAPSORT_H_INCLUDED__
\r
6 #define __IRR_HEAPSORT_H_INCLUDED__
\r
8 #include "irrTypes.h"
\r
15 //! Sinks an element into the heap.
\r
17 inline void heapsink(T*array, s32 element, s32 max)
\r
19 while ((element<<1) < max) // there is a left child
\r
21 s32 j = (element<<1);
\r
23 if (j+1 < max && array[j] < array[j+1])
\r
24 j = j+1; // take right child
\r
26 if (array[element] < array[j])
\r
28 T t = array[j]; // swap elements
\r
29 array[j] = array[element];
\r
39 //! Sorts an array with size 'size' using heapsort.
\r
41 inline void heapsort(T* array_, s32 size)
\r
43 // for heapsink we pretend this is not c++, where
\r
44 // arrays start with index 0. So we decrease the array pointer,
\r
45 // the maximum always +2 and the element always +1
\r
47 T* virtualArray = array_ - 1;
\r
48 s32 virtualSize = size + 2;
\r
53 for (i=((size-1)/2); i>=0; --i)
\r
54 heapsink(virtualArray, i+1, virtualSize-1);
\r
56 // sort array, leave out the last element (0)
\r
57 for (i=size-1; i>0; --i)
\r
60 array_[0] = array_[i];
\r
62 heapsink(virtualArray, 1, i + 1);
\r
66 } // end namespace core
\r
67 } // end namespace irr
\r