1 // Copyright (C) 2002-2005 Nikolaus Gebhardt

2 // This file is part of the "Irrlicht Engine".

3 // For conditions of distribution and use, see copyright notice in irrlicht.h

4

5 #ifndef __IRR_HEAPSORT_H_INCLUDED__

6 #define __IRR_HEAPSORT_H_INCLUDED__

7

8 #include "irrTypes.h"

9

10 namespace irr

11 {

12 namespace core

13 {

14

15 //! Sinks an element into the heap.

16 template<class T>

17 inline void heapsink(T*array, s32 element, s32 max)

18 {

19 while ((element<<1) < max) // there is a left child

20 {

21 s32 j = (element<<1);

22

23 if (j+1 < max && array[j] < array[j+1])

24 j = j+1; // take right child

25

26 if (array[element] < array[j])

27 {

28 T t = array[j]; // swap elements

29 array[j] = array[element];

30 array[element] = t;

31 element = j;

32 }

33 else

34 return;

35 }

36 }

37

38

39 //! Sorts an array with size 'size' using heapsort.

40 template<class T>

41 inline void heapsort(T* array_, s32 size)

42 {

43 // for heapsink we pretent this is not c++, where

44 // arrays start with index 0. So we decrease the array pointer,

45 // the maximum always +2 and the element always +1

46

47 T* virtualArray = array_ - 1;

48 s32 virtualSize = size + 2;

49 s32 i;

50

51 // build heap

52

53 for (i=((size-1)/2); i>=0; --i)

54 heapsink(virtualArray, i+1, virtualSize-1);

55

56 // sort array

57

58 for (i=size-1; i>=0; --i)

59 {

60 T t = array_[0];

61 array_[0] = array_[i];

62 array_[i] = t;

63 heapsink(virtualArray, 1, i + 1);

64 }

65 }

66

67 } // end namespace core

68 } // end namespace irr

69

70

71

72 #endif

73