vdk 2.4.0
vdkheap.h
1 /*
2  * ===========================
3  * VDK Visual Development Kit
4  * Version 0.4
5  * October 1998
6  * ===========================
7  *
8  * Copyright (C) 1998, Mario Motta
9  * Developed by Mario Motta <mmotta@guest.net>
10  *
11  * This library is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU Library General Public
13  * License as published by the Free Software Foundation; either
14  * version 2 of the License, or (at your option) any later version.
15  *
16  * This library is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  * Library General Public License for more details.
20  *
21  * You should have received a copy of the GNU Library General Public
22  * License along with this library; if not, write to the Free Software
23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
24  * 02111-130
25  */
26 
27 
28 #ifndef VDKHEAP_H
29 #define VDKHEAP_H
30 
31 #include <vdk/container.h>
32 
33 inline int parent(int i) { return ((i-1) >> 1); }
34 inline int left(int i) { return ((i << 1) + 1); }
35 inline int right(int i) { return ((i << 1) + 2); }
56 template <class T> class VDKHeap: public VDKContainer<T>
57 {
58  public:
63  VDKHeap(): VDKContainer<T>(0) {}
69  VDKHeap(T* source, int size);
73  virtual ~VDKHeap() {}
77  void Sort(void);
78 protected:
79  void Heapify(int i,int heapsize);
80  void BuildHeap(void);
81 };
82 
83 // make an heap copyng data from T type source vector
84 template <class T>
85 VDKHeap<T>::VDKHeap(T* source, int size): VDKContainer<T>(size)
86 {
87  for(int i = 0; i < size; i++)
88  this->data[i] = source[i];
89  BuildHeap();
90 }
91 
92 // HEAPIFY
93 template <class T>
94 void VDKHeap<T>::Heapify(int i, int heapsize)
95 {
96  int l = left(i), r = right(i), largest = i;
97  if( (l < heapsize) && (this->data[l] > this->data[i])) largest = l;
98  if( (r < heapsize) && (this->data[r] > this->data[largest])) largest = r;
99  if(largest != i)
100  {
101  T temp = this->data[i];
102  this->data[i] = this->data[largest];
103  this->data[largest] = temp;
104  Heapify(largest,heapsize);
105  }
106 }
107 
108 // BUILDHEAP
109 template <class T>
110 void VDKHeap<T>::BuildHeap(void)
111 {
112  for (int i = (this->size()-1)/2 ; i >= 0; i--)
113  Heapify(i,this->size());
114 }
115 
116 // HEAPSORT
117 template <class T>
119 {
120  int heapsize = this->size();
121  int i = heapsize-1;
122  for(; i > 0; i--)
123  {
124  T temp = this->data[0];
125  this->data[0] = this->data[i];
126  this->data[i] = temp;
127  heapsize--;
128  Heapify(0,heapsize);
129  }
130 }
131 #endif
132 
133 
134 
135 
136 
137 
provides a base class for generic containers
Definition: container.h:37
void Sort(void)
Definition: vdkheap.h:118
VDKHeap()
Definition: vdkheap.h:63
int size()
Definition: container.h:68
virtual ~VDKHeap()
Definition: vdkheap.h:73
provide a templatized Heap
Definition: vdkheap.h:56