Irrlicht 3D Engine
heapsort.h
Go to the documentation of this file.
1 // Copyright (C) 2002-2012 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 
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 
40 template<class T>
41 inline void heapsort(T* array_, s32 size)
42 {
43  // for heapsink we pretend 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, leave out the last element (0)
57  for (i=size-1; i>0; --i)
58  {
59  T t = array_[0];
60  array_[0] = array_[i];
61  array_[i] = t;
62  heapsink(virtualArray, 1, i + 1);
63  }
64 }
65 
66 } // end namespace core
67 } // end namespace irr
68 
69 #endif
70 
void heapsink(T *array, s32 element, s32 max)
Sinks an element into the heap.
Definition: heapsort.h:17
Everything in the Irrlicht Engine can be found in this namespace.
Definition: aabbox3d.h:12
signed int s32
32 bit signed variable.
Definition: irrTypes.h:70
void heapsort(T *array_, s32 size)
Sorts an array with size 'size' using heapsort.
Definition: heapsort.h:41
Self reallocating template array (like stl vector) with additional features.
Definition: irrArray.h:22