Loading...
Searching...
No Matches
heapsort.h
Go to the documentation of this file.
// Copyright (C) 2002-2012 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h
#ifndef __IRR_HEAPSORT_H_INCLUDED__
#define __IRR_HEAPSORT_H_INCLUDED__
#include "irrTypes.h"
namespace irr
{
namespace core
{
template<class T>
inline void heapsink(T*array, s32 element, s32 max)
{
while ((element<<1) < max) // there is a left child
{
s32 j = (element<<1);
if (j+1 < max && array[j] < array[j+1])
j = j+1; // take right child
if (array[element] < array[j])
{
T t = array[j]; // swap elements
array[j] = array[element];
array[element] = t;
element = j;
}
else
return;
}
}
template<class T>
inline void heapsort(T* array_, s32 size)
{
// for heapsink we pretent this is not c++, where
// arrays start with index 0. So we decrease the array pointer,
// the maximum always +2 and the element always +1
T* virtualArray = array_ - 1;
s32 virtualSize = size + 2;
s32 i;
// build heap
for (i=((size-1)/2); i>=0; --i)
heapsink(virtualArray, i+1, virtualSize-1);
// sort array, leave out the last element (0)
for (i=size-1; i>0; --i)
{
T t = array_[0];
array_[0] = array_[i];
array_[i] = t;
heapsink(virtualArray, 1, i + 1);
}
}
} // end namespace core
} // end namespace irr
#endif
irr::core::array
Self reallocating template array (like stl vector) with additional features.
Definition irrArray.h:23
irrTypes.h
irr::core
Basic classes such as vectors, planes, arrays, lists, and so on can be found in this namespace.
Definition aabbox3d.h:15
irr::core::heapsink
void heapsink(T *array, s32 element, s32 max)
Sinks an element into the heap.
Definition heapsort.h:17
irr::core::heapsort
void heapsort(T *array_, s32 size)
Sorts an array with size 'size' using heapsort.
Definition heapsort.h:41
irr
Everything in the Irrlicht Engine can be found in this namespace.
Definition aabbox3d.h:13
irr::s32
signed int s32
32 bit signed variable.
Definition irrTypes.h:66
- Irrlicht Engine Documentation © 2003-2012 by Nikolaus Gebhardt. Generated on for Irrlicht 3D Engine by Doxygen 1.15.0