5751098 [rkeene@sledge /home/rkeene/personal/school/comp-sci-ii/lab10]$ cat -n heap.h
  1 /* Roy Keene
  2    CS 2314
  3    Section 04
  4    Lab 10
  5    12 Nov 02
  6    heap.h
  7 */
  8 
  9 #include <vector>
 10 
 11 using namespace std;
 12 
 13 #ifdef DEBUG
 14 #define PrintHeap(x) cout << x ":Heap: "; for (unsigned int i=0;i<HeapData.size();i++) cout << HeapData[i] << ","; cout
	<< "\n"
 15 #else
 16 #define PrintHeap(x) /**/
 17 #endif
 18 
 19 template <typename HeapType> class Heap {
 20     public:
 21         Heap(void);
 22         ~Heap(void);
 23 
 24         bool empty(void);
 25         int size(void);
 26         void push(HeapType item);
 27         void insert(HeapType item);  // This has O(1) but breaks the heap;
 28         void heapify(void);
 29         HeapType top(void);
 30         void pop(void);
 31     private:
 32         void percolateDown(int node);
 33         void percolateUp(int node);
 34         bool IsHeap;
 35         vector<HeapType> HeapData;
 36 };
 37 
 38 template <typename HeapType> Heap<HeapType>::Heap(void) {
 39     IsHeap=true;
 40     return;
 41 }
 42 
 43 template <typename HeapType> Heap<HeapType>::~Heap(void) {
 44     return;
 45 }
 46 
 47 template <typename HeapType> bool Heap<HeapType>::empty(void) {
 48     return(HeapData.size()==0);
 49 }
 50 
 51 template <typename HeapType> int Heap<HeapType>::size(void) {
 52     return(HeapData.size());
 53 }
 54 
 55 template <typename HeapType> void Heap<HeapType>::push(HeapType item) {
 56     HeapData.push_back(item);
 57     percolateUp(HeapData.size()-1);
 58     return;
 59 }
 60 
 61 template <typename HeapType> void Heap<HeapType>::insert(HeapType item) {
 62     HeapData.push_back(item);
 63     IsHeap=false;
 64     return;
 65 }
 66 
 67 template <typename HeapType> void Heap<HeapType>::heapify(void) {
 68     int i, lidx, ridx, midx, size;
 69 
 70     if (IsHeap) return;
 71 
 72     PrintHeap("heapify1");
 73     size=HeapData.size();
 74     for (i=((size-1)/2);i>=0;i--) {
 75         midx=lidx=(2*i)+1;
 76         ridx=(2*i)+2;
 77         if (midx>=size) continue;
 78         if (ridx<size) {
 79             if (HeapData[ridx]>HeapData[lidx]) midx=ridx;
 80         }
 81         if (HeapData[midx]>HeapData[i]) {
 82             percolateDown(i);
 83         }
 84     }
 85     IsHeap=true;
 86     PrintHeap("heapify2");
 87     return;
 88 }
 89 
 90 template <typename HeapType> HeapType Heap<HeapType>::top(void) {
 91     heapify(); // NOTE: heapify()  returns immediately if IsHeap is set.
 92 
 93     return(HeapData.front());
 94 }
 95 
 96 template <typename HeapType> void Heap<HeapType>::pop(void) {
 97     PrintHeap("pop1");
 98     HeapData[0]=HeapData[HeapData.size()-1];
 99     HeapData.pop_back();
100     percolateDown(0);
101     PrintHeap("pop2");
102     return;
103 }
104 
105 template <typename HeapType> void Heap<HeapType>::percolateDown(int node) {
106     int i=node, lidx, ridx, midx, size;
107     HeapType tmp;
108 
109     PrintHeap("percdown");
110     while (1) {
111         if (i>=(size=HeapData.size())) break;
112         midx=lidx=(2*i)+1;
113         ridx=(2*i)+2;
114         if (lidx>=size) break;
115         if (ridx<size) {
116             if (HeapData[ridx]>HeapData[lidx]) midx=ridx;
117         }
118         if (HeapData[midx]>HeapData[i]) {
119             tmp=HeapData[i];
120             HeapData[i]=HeapData[midx];
121             HeapData[midx]=tmp;
122         } else {
123             if (IsHeap) break;
124         }
125         i=midx;
126     }
127     return;
128 }
129 
130 template <typename HeapType> void Heap<HeapType>::percolateUp(int node) {
131     int i=node, pidx;
132     HeapType tmp;
133 
134     PrintHeap("percdown");
135 
136     while (1) {
137         pidx=((i-1)/2);
138 #if 0
139         if (!IsHeap) {
140 // XXX: Should we do some L/R comparisons here ?            
141         }
142 #endif
143         if (HeapData[i]>HeapData[pidx]) {
144             tmp=HeapData[i];
145             HeapData[i]=HeapData[pidx];
146             HeapData[pidx]=tmp;
147         } else {
148             if (IsHeap) break;
149         }
150 
151         if (pidx==0) break;
152         i=pidx;
153     }
154     return;
155 }
5751099 [rkeene@sledge /home/rkeene/personal/school/comp-sci-ii/lab10]$
Click here to go back to the directory listing.
Click here to download this file.
last modified: 2002-11-13 00:10:03