4 public TaggedTree ttree;
13 public FibHeap(int degree,
21 public boolean isEmpty() {
22 return this.degree == 0;
26 return this.ttree.tree.root;
29 public FibHeap insertFH(int x) {
30 TaggedTree tt = new TaggedTree(0, new Tree(x, null));
31 FibHeap fh = new FibHeap(1, tt, null);
33 return this.meldFH(fh);
36 public FibHeap meldFH(FibHeap fh) {
40 int root1 = fh.ttree.tree.root;
41 int root2 = this.ttree.tree.root;
42 TaggedTree root = null;
43 Vector forest = fh.forest;
45 forest = new Vector();
49 forest.insertElementAt(this.ttree, 0);
52 forest.insertElementAt(fh.ttree, 0);
54 if(this.forest != null) {
55 for(int i = 0; i < this.forest.size(); i++) {
56 forest.addElement(this.forest.elementAt(i));
59 return new FibHeap(fh.degree+this.degree, root, forest);
63 private void insert(Vector a,
65 int index = tt.degree;
66 if(a.elementAt(index) == null) {
67 a.setElementAt(tt.tree, index);
69 Tree at = (Tree)a.elementAt(index);
70 a.setElementAt(null, index);
71 // link these two tree
72 Tree it = tt.tree.link(at);
73 TaggedTree itt = new TaggedTree(index+1, it);
78 private FibHeap getMin_t(Vector a,
85 return new FibHeap(this.degree-1, new TaggedTree(mini, mint), b);
87 Tree at = (Tree)a.elementAt(i);
89 return getMin_t(a, mini, mint, b, i+1, d);
91 if(mint.root <= at.root) {
92 b.insertElementAt(new TaggedTree(i, at), 0);
93 return getMin_t(a, mini, mint, b, i+1, d);
95 b.insertElementAt(new TaggedTree(mini, mint), 0);
96 return getMin_t(a, i, at, b, i+1, d);
102 private int locallog(int n) {
106 return 1 + locallog(n/2);
110 public FibHeap deleteMinFH() {
115 if(this.degree == 1) {
116 return new FibHeap();
118 // newArray (0,d) Zero >>= \a -> applyToAll (ins a) f
119 // Allocate an array indexed by degrees.
120 int d = locallog(this.degree - 1);
121 Vector a = new Vector(d+1);
122 for(int i = 0; i < d+1; i++) {
125 // Insert every tree into this array. If, when inserting a tree of
126 // degree k, there already exists a tree of degree k, link the
127 // two trees and reinsert the new larger tree.
128 for(int i = 0; i < this.forest.size(); i++) {
129 TaggedTree tt = (TaggedTree)this.forest.elementAt(i);
132 // sequence (map (ins a) (getChildren tt))
133 Vector vec = this.ttree.getChildren();
134 for(int i = 0; i < vec.size(); i++) {
135 TaggedTree tt = (TaggedTree)vec.elementAt(i);
138 // getMin a >>= \ (tt,f) -> return (FH (n-1) tt f))
139 Tree test = (Tree)a.elementAt(d);
144 return getMin_t(a, d, test, new Vector(), 0, d);
148 private Vector combine(int index,
153 return startup(index+1, next, rest);
154 } else if (ts.size() == 1) {
155 Vector vec = startup(index+1, next, rest);
156 vec.insertElementAt(new TaggedTree(index, (Tree)ts.elementAt(0)), 0);
159 Tree t1 = (Tree)ts.elementAt(0);
160 Tree t2 = (Tree)ts.elementAt(1);
161 next.insertElementAt(t1.link(t2), 0);
162 Vector nts = new Vector();
163 for(int i = 2; i < ts.size(); i++) {
164 nts.addElement(ts.elementAt(i));
166 return combine(index, nts, next, rest);
170 private Vector startup(int index,
174 if(rest.size() == 0) {
177 Vector tts = (Vector)rest.elementAt(0);
178 Vector nrest = new Vector();
179 for(int i = 1; i < rest.size(); i++) {
180 nrest.addElement(rest.elementAt(i));
182 return startup(index+1, tts, nrest);
185 if(rest.size() == 0) {
186 return combine(index, ts, new Vector(), new Vector());
188 Vector tts = (Vector)rest.elementAt(0);
189 Vector nrest = new Vector();
190 for(int i = 1; i < rest.size(); i++) {
191 nrest.addElement(rest.elementAt(i));
193 return combine(index, ts, tts, nrest);
198 private FibHeap chooseMin(FibHeap fh,
201 if(fh.ttree.tree.root <= tt.tree.root) {
202 fh.forest.insertElementAt(tt, 0);
203 rfh = new FibHeap(this.degree-1, fh.ttree, fh.forest);
205 fh.forest.insertElementAt(fh.ttree, 0);
206 rfh = new FibHeap(this.degree-1, tt, fh.forest);
211 public FibHeap deleteMinFH_t() {
216 if(this.degree == 1) {
217 return new FibHeap();
219 // The second version of deleteMin uses accumArray to group trees of like
220 // size. It then performs the linking and all remaining steps purely
222 int d = locallog(this.degree - 1);
223 // arrange a 2 dimentional array to group the trees
224 Vector a = new Vector(d+1);
225 for(int i = 0; i < d+1; i++) {
226 a.addElement(new Vector());
228 for(int i = 0; i < this.forest.size(); i++) {
229 TaggedTree tt = (TaggedTree)this.forest.elementAt(i);
231 ((Vector)a.elementAt(de)).addElement(tt.tree);
233 // sequence (map (ins a) (getChildren tt))
234 Vector vec = this.ttree.getChildren();
235 for(int i = 0; i < vec.size(); i++) {
236 TaggedTree tt = (TaggedTree)vec.elementAt(i);
238 ((Vector)a.elementAt(de)).addElement(tt.tree);
240 Vector ts = (Vector)a.elementAt(0);
241 Vector na = new Vector();
242 for(int i = 1; i < a.size(); i++) {
243 na.addElement(a.elementAt(i));
245 Vector vvec = startup(0, ts, na);
248 TaggedTree rtt = (TaggedTree)vvec.elementAt(0);
249 FibHeap rfh = new FibHeap(this.degree-1, rtt, new Vector());
250 Vector nvvec = new Vector();
251 for(int i = 1; i < vvec.size(); i++) {
252 nvvec.addElement(vvec.elementAt(i));
255 while(vvec.size() != 0) {
256 rfh = chooseMin(rfh, (TaggedTree)vvec.elementAt(0));
257 Vector tvvec = new Vector();
258 for(int i = 1; i < vvec.size(); i++) {
259 tvvec.addElement(vvec.elementAt(i));