Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | Related Pages

vdkheap.h

00001 /* 00002 * =========================== 00003 * VDK Visual Development Kit 00004 * Version 0.4 00005 * October 1998 00006 * =========================== 00007 * 00008 * Copyright (C) 1998, Mario Motta 00009 * Developed by Mario Motta <mmotta@guest.net> 00010 * 00011 * This library is free software; you can redistribute it and/or 00012 * modify it under the terms of the GNU Library General Public 00013 * License as published by the Free Software Foundation; either 00014 * version 2 of the License, or (at your option) any later version. 00015 * 00016 * This library is distributed in the hope that it will be useful, 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00019 * Library General Public License for more details. 00020 * 00021 * You should have received a copy of the GNU Library General Public 00022 * License along with this library; if not, write to the Free Software 00023 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 00024 * 02111-130 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 // make an heap copyng data from T type source vector 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 // HEAPIFY 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 // BUILDHEAP 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 // HEAPSORT 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

Generated on Tue Aug 17 12:39:51 2004 for vdk 2.4.0 by doxygen 1.3.7