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
33inline int parent(int i) { return ((i-1) >> 1); }
34inline int left(int i) { return ((i << 1) + 1); }
35inline int right(int i) { return ((i << 1) + 2); }
56template <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);
78protected:
79 void Heapify(int i,int heapsize);
80 void BuildHeap(void);
81};
82
83// make an heap copyng data from T type source vector
84template <class T>
85VDKHeap<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
93template <class T>
94void 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
109template <class T>
110void 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
117template <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:38
int size()
Definition: container.h:68
provide a templatized Heap
Definition: vdkheap.h:57
virtual ~VDKHeap()
Definition: vdkheap.h:73
VDKHeap()
Definition: vdkheap.h:63
void Sort(void)
Definition: vdkheap.h:118