HeapSort (C++ Template関数実装)

久しぶりに、プログラミング。
今日はいままで自分で書いたことなかったヒープソート。

#ifndef __HEAPSORT_H__
#define __HEAPSORT_H__

template 
void MaxHeapify( T* target, unsigned int index , unsigned int length) {
	unsigned int l = index<<1;
	unsigned int r = (index<<1)+1;
	unsigned int max = index;
	if( l < length && target[index] < target[l]	){
		max = l;
	}
	if( r < length && target[max] < target[r] ){
		max = r;
	}
	if( index != max ){
		T tmp = target[index];
		target[index] = target[max];
		target[max] = tmp;
		MaxHeapify( target, max, length );	
	}

	return;
}

template 
void BuildMaxHeap( T* target, unsigned int length ){
	for( unsigned int i = (length-1)/2; true ; i-- ){
		MaxHeapify( target, i, length );
		if( 0 == i ){
			break;
		}
	}
}


template 
void HeapSort( T* target, unsigned int length){
	BuildMaxHeap( target , length );
	while(length != 0 ){
		T tmp = target[length-1]; 
		target[length-1] = target[0];
		target[0] = tmp;
		length--;
		MaxHeapify(target, 0, length );
	}
}

#endif

includeしてから次ように使う。

unsigned char buf[] = {5,7,10,8,11};
HeapSort( buf, 5 );
//ここでbuf内はソート済み。