Problème Tas de Fibonacci
Bonjour,
Je cherche à implémenter le tas de Fibonacci en Java avec les collections standards de Java mais je rencontre un problème avec la méthode consolider.
J'ai une erreur du type IndexOutOfBounds pour array;
Fibonacci.java
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
| import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class Fibonacci {
private static final double oneOverLogPhi =
1.0 / Math.log((1.0 + Math.sqrt(5.0)) / 2.0);
private Noeud min;
private ArrayList<Noeud> racines;
private int taille;
public Fibonacci (){
super();
min = null;
racines = new ArrayList<Noeud> ();
}
public Noeud findMinimum (){
return min;
}
public static Fibonacci union (Fibonacci a, Fibonacci b){
Fibonacci t = new Fibonacci ();
t.min = a.min;
t.racines.addAll(b.racines);
t.racines.addAll(a.racines);
if (a.min == null | b.min !=null & b.min.getClé() < a.min.getClé()){
t.min = b.min;
}
t.taille = a.taille + b.taille;
a = null;
b = null;
return t;
}
public void inserer (Noeud n){
if (min == null || n.getClé() < min.getClé()){
min = n;
}
taille += 1;
racines.add(n);
}
private void relier (Noeud y, Noeud x){
racines.remove(y);
y.setPere(x);
x.getEnfants().add(y);
y.setMarque (false);
}
public void couper (Noeud x, Noeud y){
y.getEnfants().remove(x);
racines.add(x);
x.setPere(null);
x.setMarque(false);
}
public void couperEnCascade (Noeud y){
Noeud z = y.getPere ();
if (z != null){
if (!z.estMarque()){
z.setMarque(true);
}
else {
couper(y, z);
couperEnCascade(z);
}
}
}
public void diminueCle (Noeud x, Integer valeur) {
if (valeur > x.getClé()){
throw new Error("new key is greater than current key");
}
x.setClé(valeur);
Noeud y = x.getPere();
if (y != null && x.getClé() < y.getClé()){
couper(x, y);
couperEnCascade(y);
}
if (x.getClé() < min.getClé()){
min = x;
}
}
private void consolider (){
//System.out.println(taille);
int degreMax = ((int) Math.floor(Math.log(taille) * oneOverLogPhi)) + 2;
//System.out.println(((int) Math.floor(Math.log(taille) * oneOverLogPhi)) + 1);
List<Noeud> array = new ArrayList<Noeud> (degreMax);
for (int i = 0; i < degreMax; i++){
array.add(null);
}
int numRoots = racines.size();
Noeud x = min;
while (numRoots > 0) {
int d = x.getEnfants().size();
Noeud next = racines.get(racines.indexOf(x) + 1 == racines.size() ? 0 : racines.indexOf(x) + 1);
for (;;) {
System.out.println ( x + " d : " + d);
Noeud y = array.get(d);
if (y == null) {
// Nope.
break;
}
if (x.getClé() > y.getClé()) {
Noeud temp = y;
y = x;
x = temp;
}
this.relier(y, x);
array.set(d, null);
d++;
}
array.set(d, x);
x = next;
numRoots--;
}
min = null;
for (int i = 0; i < array.size(); i++){
if (array.get(i) != null){
racines.add(array.get(i));
if (min == null || array.get(i).getClé() < min.getClé()){
min = array.get(i);
}
}
}
}
private void echanger (Noeud x, Noeud y){
Noeud tmp = x;
x = y;
y = tmp;
}
public Noeud extraireMinimum(){
Noeud z = min;
if (z != null){
for (Noeud enfant : z.getEnfants()){
enfant.setPere(null);
racines.add(enfant);
}
z.getEnfants().clear();
}
int index = racines.indexOf(z);
racines.remove(z);
if (racines.size() == 0){
min = null;
}else {
min = racines.get(index+1);
consolider();
}
taille--;
return z;
}
public void supprimer(Noeud n){
diminueCle(n, Integer.MIN_VALUE);
extraireMinimum();
}
boolean isEmpty (){
return min == null;
}
} |
Noeud.java
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| public class Noeud {
private boolean marque;
private Noeud pere;
private LinkedList<Noeud> enfants;
private Integer clé;
private Integer donnée;
public Noeud (int sommet,int valeur ){
this.clé = valeur;
this.marque = false;
this.pere = null;
enfants = new LinkedList<> ();
this.donnée = sommet;
}
public Integer getClé (){
return clé;
}
public LinkedList<Noeud> getEnfants() {
return enfants;
}
public void setMarque(boolean b) {
this.marque = b;
}
public void setPere(Noeud pere) {
this.pere = pere;
}
public Noeud getPere (){
return pere;
}
public boolean estMarque (){
return marque;
}
public void setClé(Integer valeur) {
this.clé = valeur;
}
public Integer getDonnée (){
return donnée;
}
@Override
public String toString (){
return new String (this.donnée+ " " + this.clé);
}
} |
Quelqu'un saurait-il m'indiquer d'où peut venir l'erreur ?
Merci d'avance pour votre aide.
