source: GTP/trunk/App/Demos/Illum/pathmap/Heap.hpp @ 2197

Revision 2197, 3.1 KB checked in by szirmay, 18 years ago (diff)
Line 
1// Graphics Programming Methods
2// An Effective kd-tree Implementation
3// László Szécsi
4// 2003.
5
6// template class for a min-heap
7// E must define operators for comparison
8
9#pragma once
10
11template < class E >
12class Heap
13{
14public:
15        Heap ( int maxNumber);
16    ~Heap ();
17
18    inline bool insert ( const E &newElement );
19    inline E removeMin ();
20    inline E getMin ();
21
22    inline int isEmpty () const;
23    inline int isFull () const;
24
25private:
26    // Data members
27        int maxSize,   // Maximum number of elements in the heap
28        size;      // Actual number of elements in the heap
29    E *element;   // Array containing the heap elements
30};
31
32template<class E>
33Heap<E>::Heap( int maxNumber)
34{
35        maxSize = maxNumber;
36    size = 0;
37        element = new E [maxSize];
38}
39
40template <class E>
41Heap<E>::~Heap()
42{
43        delete [] element;
44}
45
46template<class E>
47bool Heap<E>::insert(const E & newElement)
48{
49        int currpos = size;
50        int parentpos = (size -1)/2;
51        int isPosition = 0;
52        if ( isFull() )
53    {
54                return false;
55    }
56        // Inserts newElement into the heap;
57        element[size] = newElement;
58        size ++;
59   
60        // if newElement is lower, move it upward
61        while ( currpos > 0 && !isPosition)
62        {
63                if ( element[currpos] >= element[parentpos] )
64                        isPosition = 1;
65                else
66                {
67                        element[currpos] = element[parentpos];
68                        element[parentpos] = newElement;
69                        currpos = parentpos;
70                        parentpos = ( currpos -1 )/2 ;
71                }
72        }
73        return true;
74}
75
76template<class E>
77E Heap<E>::getMin()
78{
79        return element[0];
80}
81
82template<class E>
83E Heap<E>::removeMin()
84{
85        E delItem, temp;
86        int currpos, lpos, rpos, isPosition = 0;
87        if ( isEmpty() )
88        {
89                exit(1);
90        }
91
92        // removes the root
93        delItem = element[0];
94        size --;
95
96        // replace the root with the bottom right-most element
97        element[0] = element[size];
98        temp = element[0];
99
100        // set the current position and left and right child positions
101        currpos = 0;
102        lpos = 2*currpos + 1;
103        rpos = 2*currpos + 2;
104
105        // if the replacement is not proper, move it downward until the
106        // the properties that define a min-heap are restored
107        while ( size > currpos+1 && !isPosition )
108        {
109        temp = element[currpos];         
110                if ( rpos < size )
111                {
112                        if ( element[currpos] > element[lpos] ||
113                                element[currpos] > element[rpos] )
114                        {
115                                if ( element[lpos] < element[rpos] )
116                                {
117                                        element[currpos] = element[lpos];
118                                        element[lpos] = temp;
119                                        currpos = lpos;
120                                }
121                                else
122                                {
123                                        element[currpos] = element[rpos];
124                                        element[rpos] = temp;
125                                        currpos = rpos;
126                                }
127                        }
128                }
129                else if ( lpos < size && element[lpos] < element[currpos] )
130                {
131                        element[currpos] = element[lpos];
132                        element[lpos] = temp;
133                        currpos = lpos;
134                }
135                temp = element[currpos];
136                lpos = 2*currpos +1;
137                rpos = 2*currpos +2;
138
139                if ( (lpos >= size)
140                        ||
141                        element[currpos] <= element[lpos]
142                        &&
143                        element[currpos] <= element[rpos])
144                        isPosition = 1;
145        }
146        return delItem;
147}
148
149template<class E>
150int Heap<E>:: isEmpty() const
151{
152        return size==0;
153}
154
155template<class E>
156int Heap<E>::isFull() const
157{
158        return size == maxSize;
159}
160
Note: See TracBrowser for help on using the repository browser.