00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
#ifndef VDKHEAP_H
00029
#define VDKHEAP_H
00030
00031
#include <vdk/container.h>
00032
00033
inline int parent(
int i) {
return ((i-1) >> 1); }
00034
inline int left(
int i) {
return ((i << 1) + 1); }
00035
inline int right(
int i) {
return ((i << 1) + 2); }
00056 template <
class T>
class VDKHeap:
public VDKContainer<T>
00057 {
00058
public:
00063 VDKHeap():
VDKContainer<T>(0) {}
00069
VDKHeap(T* source,
int size);
00073 virtual ~VDKHeap() {}
00077
void Sort(
void);
00078
protected:
00079
void Heapify(
int i,
int heapsize);
00080
void BuildHeap(
void);
00081 };
00082
00083
00084
template <
class T>
00085 VDKHeap<T>::VDKHeap(T* source,
int size):
VDKContainer<T>(size)
00086 {
00087
for(
int i = 0; i < size; i++)
00088 data[i] = source[i];
00089 BuildHeap();
00090 }
00091
00092
00093
template <
class T>
00094
void VDKHeap<T>::Heapify(
int i,
int heapsize)
00095 {
00096
int l = left(i), r = right(i), largest = i;
00097
if( (l < heapsize) && (data[l] > data[i])) largest = l;
00098
if( (r < heapsize) && (data[r] > data[largest])) largest = r;
00099
if(largest != i)
00100 {
00101 T temp = data[i];
00102 data[i] = data[largest];
00103 data[largest] = temp;
00104 Heapify(largest,heapsize);
00105 }
00106 }
00107
00108
00109
template <
class T>
00110
void VDKHeap<T>::BuildHeap(
void)
00111 {
00112
for (
int i = (
size()-1)/2 ; i >= 0; i--)
00113 Heapify(i,
size());
00114 }
00115
00116
00117
template <
class T>
00118 void VDKHeap<T>::Sort(
void)
00119 {
00120
int heapsize =
size();
00121
int i = heapsize-1;
00122
for(; i > 0; i--)
00123 {
00124 T temp = data[0];
00125 data[0] = data[i];
00126 data[i] = temp;
00127 heapsize--;
00128 Heapify(0,heapsize);
00129 }
00130 }
00131
#endif
00132
00133
00134
00135
00136
00137