Irrlicht 3D Engine
 
Loading...
Searching...
No Matches
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
10namespace irr
11{
12namespace core
13{
14
16template<class T>
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
40template<class T>
41inline 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)
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
Axis aligned bounding box in 3d dimensional space.
Definition aabbox3d.h:22
Self reallocating template array (like stl vector) with additional features.
Definition irrArray.h:23
void heapsink(T *array, s32 element, s32 max)
Sinks an element into the heap.
Definition heapsort.h:17
void heapsort(T *array_, s32 size)
Sorts an array with size 'size' using heapsort.
Definition heapsort.h:41
Everything in the Irrlicht Engine can be found in this namespace.
Definition aabbox3d.h:13
signed int s32
32 bit signed variable.
Definition irrTypes.h:66