Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members  

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 Sat May 4 23:45:42 2002 for vdk 2.0.1 by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002