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
package edu.caltech.cs2.datastructures;
import edu.caltech.cs2.interfaces.IDictionary;
import edu.caltech.cs2.interfaces.IPriorityQueue;
import java.util.Iterator;
public class MinFourHeap<E> implements IPriorityQueue<E> {
private static final int DEFAULT_CAPACITY = 10;
private static final int GROWTH_FACTOR = 2;
private int size;
private PQElement<E>[] data;
private IDictionary<E, Integer> keyToIndexMap;
/**
* Creates a new empty heap with DEFAULT_CAPACITY.
*/
public MinFourHeap() {
this.size = 0;
this.data = new PQElement[DEFAULT_CAPACITY];
this.keyToIndexMap = new ChainingHashDictionary<>(MoveToFrontDictionary::new);
}
@Override
public void increaseKey(PQElement<E> key) {
if (!this.keyToIndexMap.containsKey(key.data)) {
throw new IllegalArgumentException("Can't modify a nonexistent element!");
}
if (key.priority > this.data[this.keyToIndexMap.get(key.data)].priority) {
this.data[this.keyToIndexMap.get(key.data)] = key;
percDown(this.keyToIndexMap.get(key.data));
}
}
@Override
public void decreaseKey(PQElement<E> key) {
if (!this.keyToIndexMap.containsKey(key.data)) {
throw new IllegalArgumentException("Can't modify a nonexistent element!");
}
else if (key.priority < this.data[this.keyToIndexMap.get(key.data)].priority) {
this.data[this.keyToIndexMap.get(key.data)] = key;
percUp(this.keyToIndexMap.get(key.data));
}
}
@Override
public boolean enqueue(PQElement<E> epqElement) {
if (this.keyToIndexMap.containsKey(epqElement.data)) {
throw new IllegalArgumentException("This key is already in MinFourHeap!");
}
else if (this.size >= this.data.length) {
PQElement<E>[] temp = new PQElement[this.size * GROWTH_FACTOR];
System.arraycopy(this.data, 0, temp, 0, this.size);
this.data = temp;
}
this.data[this.size] = epqElement;
this.keyToIndexMap.put(epqElement.data, this.size);
this.size++;
percUp(this.size - 1);
return true;
}
@Override
public PQElement<E> dequeue() {
if (this.size == 0) {
return null;
}
else if (this.size == 1) {
PQElement<E> root = this.data[0];
this.size--;
this.keyToIndexMap.remove(root.data);
this.data[0] = null;
return root;
}
PQElement<E> root = this.data[0];
this.size--;
this.keyToIndexMap.remove(root.data);
this.data[0] = this.data[this.size];
this.keyToIndexMap.put(this.data[0].data, 0);
percDown(0);
return root;
}
@Override
public PQElement<E> peek() {
if (this.size == 0) {
throw new IllegalArgumentException("Empty array, nothing to peek!");
}
return data[0];
}
@Override
public int size() {
return this.size;
}
@Override
public Iterator<PQElement<E>> iterator() {
return null;
}
private boolean hasChild (int index, int childNum) {
int childIndex = ((4 * index) + childNum);
return (childIndex < this.size && childIndex > 0);
}
private void percUp(int idx) {
while ((idx - 1) / 4 >= 0 && this.data[(idx - 1) / 4].priority > this.data[idx].priority) {
int parentidx = (idx - 1) / 4;
PQElement temp = data[parentidx];
data[parentidx] = data[idx];
data[idx] = temp;
int temp2 = this.keyToIndexMap.get(data[parentidx].data);
this.keyToIndexMap.put(data[parentidx].data, this.keyToIndexMap.get(data[idx].data));
this.keyToIndexMap.put(data[idx].data, temp2);
idx = (idx - 1) / 4;;
}
}
private void percDown(int idx) {
while (hasChild(idx, 1)) {
int parentidx = 0;
int minchildIndex = ((4 * idx) + 1);
if (minchildIndex >= this.size) {
minchildIndex = 1;
}
double min = this.data[minchildIndex].priority;
int minChildIndex = minchildIndex;
int childNum = 2;
while (hasChild(idx, childNum) && childNum <= 4) {
int childIndex = ((4 * idx) + childNum);
if(this.data[childIndex].priority < min) {
min = this.data[childIndex].priority;
minChildIndex = childIndex;
}
childNum++;
}
parentidx = minChildIndex;
PQElement smallestChild = this.data[parentidx];
if (smallestChild.priority < this.data[idx].priority) {
PQElement temp = data[parentidx];
data[parentidx] = data[idx];
data[idx] = temp;
int temp2 = this.keyToIndexMap.get(data[parentidx].data);
this.keyToIndexMap.put(data[parentidx].data, this.keyToIndexMap.get(data[idx].data));
this.keyToIndexMap.put(data[idx].data, temp2);
} else {
break;
}
idx = parentidx;
}
}
}