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