00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 package com.meapsoft;
00024
00025 import java.util.Arrays;
00026 import java.util.Collection;
00027 import java.util.Comparator;
00028 import java.util.Vector;
00029
00030
00031
00032
00045 public abstract class Heap extends Vector
00046 {
00047
00048
00049 private Comparator comp = null;
00050
00051
00052
00053
00054
00055 protected boolean isHeap = true;
00056
00060 public Heap()
00061 {
00062 super();
00063 }
00064
00070 public Heap(Comparator c)
00071 {
00072 super();
00073 comp = c;
00074 }
00075
00079 public Heap(int capacity)
00080 {
00081 super(capacity);
00082 }
00083
00088 public Heap(Collection c)
00089 {
00090 super();
00091 addAll(c);
00092 }
00093
00097 public Object remove(int index)
00098 {
00099 if(!isHeap)
00100 rebuildHeap();
00101
00102 Object o = get(index);
00103
00104 set(index, get(size()-1));
00105 removeElementAt(size()-1);
00106
00107 heapify(index);
00108
00109 return o;
00110 }
00111
00116 public boolean remove(Object o)
00117 {
00118 boolean found = false;
00119 for(int i = 0; i < size(); i++)
00120 {
00121 if(o == null ? get(i) == null : o.equals(get(i)))
00122 {
00123 found = true;
00124 remove(i);
00125
00126 break;
00127 }
00128 }
00129
00130 return found;
00131 }
00132
00136 public boolean add(Object o)
00137 {
00138 if(!isHeap)
00139 rebuildHeap();
00140
00141 boolean b = super.add(o);
00142
00143 for(int node = size()-1; node > 0;)
00144 {
00145 int cmp;
00146 int parent = (int)((node-1)/2);
00147
00148 if(cmp(node, parent) < 0)
00149 {
00150
00151 Object tmp = get(node);
00152 set(node, get(parent));
00153 set(parent, tmp);
00154 }
00155
00156 node = parent;
00157 }
00158
00159
00160
00161
00162
00163
00164 return b;
00165 }
00166
00167
00171 public boolean addAll(Collection c)
00172 {
00173 boolean b = super.addAll(c);
00174
00175 rebuildHeap();
00176
00177 return(b);
00178 }
00179
00187 public void rebuildHeap()
00188 {
00189
00190 for(int i = (int)(size()/2); i >= 0; i--)
00191 heapify(i);
00192
00193 isHeap = true;
00194 }
00195
00202 public void sort()
00203 {
00204 Object[] a = toArray();
00205 if(comp == null)
00206 Arrays.sort(a);
00207 else
00208 Arrays.sort(a, comp);
00209
00210 elementData = a;
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230 isHeap = false;
00231 }
00232
00237 protected int cmp(int node1, int node2)
00238 {
00239 int c = 0;
00240 if(comp != null)
00241 c = comp.compare(get(node1), get(node2));
00242 else
00243 c = ((Comparable)get(node1)).compareTo(get(node2));
00244
00245 return c;
00246 }
00247
00252 private void heapify(int node, int size)
00253 {
00254 if(node > size)
00255 return;
00256
00257 int left = (node+1)*2-1;
00258 int right = (node+1)*2;
00259
00260 int minidx = node;
00261
00262 if(left < size && cmp(left, node) <= 0)
00263 minidx = left;
00264 if(right < size && cmp(right, node) <= 0 && cmp(right, left) <= 0)
00265 minidx = right;
00266
00267 if(minidx != node)
00268 {
00269
00270 Object tmp = get(node);
00271 set(node, get(minidx));
00272 set(minidx, tmp);
00273
00274 heapify(minidx, size);
00275 }
00276 }
00277
00281 private void heapify(int node)
00282 {
00283 heapify(node, size());
00284 }
00285
00290 public boolean isHeap()
00291 {
00292 return isHeap;
00293 }
00294 }