Heapsort

Template functions for heapsorting an array of index-objects indexing an array of value-objects comparable by "<". More...

Functions
template<class I , class V >
void	CH_Tools::heapify (int i, int n, I &ind, const V &val, bool non_decreasing=true)
	Heapify element i (in 0,...,n-1) in ind, so that afterwards val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for the subtree with root i. More...
template<class I , class V >
void	CH_Tools::build_heap (int n, I &ind, const V &val, bool non_decreasing=true)
	Build a heap out of ind[0] to ind[n-1], so that val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for all j. More...
template<class I , class V >
void	CH_Tools::heapsort (int n, I &ind, const V &val, bool non_decreasing=true)
	Sort ind[0]...ind[n-1] so that val[ind[i]]<=val[ind[j]] for 0<=i<j<n. More...
template<class I , class V >
void	CH_Tools::heapify (int i, int n, I *ind, const V *val, bool non_decreasing=true)
	More efficient variant for pointers to indices and values: Heapify element i (in 0,...,n-1) in ind, so that afterwards val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for the subtree with root i. More...
template<class I , class V >
void	CH_Tools::build_heap (int n, I *ind, const V *val, bool non_decreasing=true)
	More efficient variant for pointers to indices and values: Build a heap out of ind[0] to ind[n-1], so that val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for all j. More...
template<class I , class V >
void	CH_Tools::heapsort (int n, I *ind, const V *val, bool non_decreasing=true)
	More efficient variant for pointers to indices and values: Sort ind[0]...ind[n-1] so that val[ind[i]]<=val[ind[j]] for 0<=i<j<n. More...

Detailed Description

Template functions for heapsorting an array of index-objects indexing an array of value-objects comparable by "<".

For given

• n : number of indices to be sorted
• ind : a class indexable by integers, a function swap(ind[i],ind[j]) is required which swaps the contents of ind[i] and ind[j]
• val : class indexable by elements of ind, for two vals val[i] and val[j] operators "<" and ">" (val[i]<val[j]) yielding 0/1 must be defined
• non_decreasing : if true (default) the indices give a a non_decreasing sorting, otherwise non_increasing

the routines sort the first n entries in the index array such that

   val[ind[i]]<=val[ind[j]] for 0<=i<j<n  (non_decreasing==true)  

or val[ind[i]]>=val[ind[j]] for 0<=i<j<n (non_decreasing==false)

Function Documentation

build_heap() [1/2]

template<class I , class V >

void CH_Tools::build_heap ( int  n, I &  ind, const V &  val, bool  non_decreasing = true  )

inline

Build a heap out of ind[0] to ind[n-1], so that val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for all j.

Parameters

n	index array goes from 0 .. n-1
ind	index array into val, rearrangeable by swap(ind[j],ind[k])
val	value array index by ind[j], comparable by "<"
non_decreasing	if true (default) sort in non_decreasing order

References CH_Tools::heapify().

Referenced by CH_Tools::heapsort().

build_heap() [2/2]

template<class I , class V >

void CH_Tools::build_heap ( int  n, I *  ind, const V *  val, bool  non_decreasing = true  )

inline

More efficient variant for pointers to indices and values: Build a heap out of ind[0] to ind[n-1], so that val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for all j.

Parameters

n	index array goes from 0 .. n-1
ind	index array into val, rearrangeable by assignments
val	value array index by ind[j], comparable by "<"
non_decreasing	if true (default) sort in non_decreasing order

References CH_Tools::heapify().

heapify() [1/2]

template<class I , class V >

void CH_Tools::heapify ( int  i, int  n, I &  ind, const V &  val, bool  non_decreasing = true  )

inline

Heapify element i (in 0,...,n-1) in ind, so that afterwards val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for the subtree with root i.

Parameters

i	index of element to be heapfied (indexing starts with 0)
n	index array goes from 0 .. n-1
ind	index array into val, rearrangeable by swap(ind[j],ind[k])
val	value array index by ind[j], comparable by "<"
non_decreasing	if true (default) sort in non_decreasing order

References CH_Matrix_Classes::swap().

Referenced by CH_Tools::build_heap(), and CH_Tools::heapsort().

heapify() [2/2]

template<class I , class V >

void CH_Tools::heapify ( int  i, int  n, I *  ind, const V *  val, bool  non_decreasing = true  )

inline

More efficient variant for pointers to indices and values: Heapify element i (in 0,...,n-1) in ind, so that afterwards val[ind[j]]>=max(val[ind[2*j+1]],val[ind[2*j+2]] for the subtree with root i.

Parameters

i	index of element to be heapfied (indexing starts with 0)
n	index array goes from 0 .. n-1
ind	index array into val, rearrangeable by assignments
val	value array index by ind[j], comparable by "<"
non_decreasing	if true (default) sort in non_decreasing order

heapsort() [1/2]

template<class I , class V >

void CH_Tools::heapsort ( int  n, I &  ind, const V &  val, bool  non_decreasing = true  )

inline

Sort ind[0]...ind[n-1] so that val[ind[i]]<=val[ind[j]] for 0<=i<j<n.

Parameters

n	index array goes from 0 .. n-1
ind	index array into val, rearrangeable by swap(ind[j],ind[k])
val	value array index by ind[j], comparable by "<"
non_decreasing	if true (default) sort in non_decreasing order

References CH_Tools::build_heap(), CH_Tools::heapify(), and CH_Matrix_Classes::swap().

heapsort() [2/2]

template<class I , class V >

void CH_Tools::heapsort ( int  n, I *  ind, const V *  val, bool  non_decreasing = true  )

inline

More efficient variant for pointers to indices and values: Sort ind[0]...ind[n-1] so that val[ind[i]]<=val[ind[j]] for 0<=i<j<n.

Parameters

n	index array goes from 0 .. n-1
ind	index array into val, rearrangeable by assignments
val	value array index by ind[j], comparable by "<"
non_decreasing	if true (default) sort in non_decreasing order

References CH_Tools::build_heap(), CH_Tools::heapify(), and CH_Matrix_Classes::swap().