-
Notifications
You must be signed in to change notification settings - Fork 2
/
BinaryMinHeap.java
207 lines (183 loc) · 4.39 KB
/
BinaryMinHeap.java
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
package com.algorithm.playground.data.structure;
import java.util.*;
/**
* An implementation for MapHeap data structure based on idea from this video:
* https://www.youtube.com/watch?v=lAXZGERcDf4&list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j
*
* @param <K> type of key
* @param <V> type of weight
*/
public class BinaryMinHeap<K, V extends Comparable<V>> {
/** Heap */
private List<Tuple2<K, V>> values;
/** Map key to index in the heap */
private Map<K, Integer> indexes;
public BinaryMinHeap() {
values = new ArrayList<>();
indexes = new HashMap<>();
}
/**
* doesn't remove the minimum value from the heap
*
* @return a tuple of minimum key and it's weight
*/
public Tuple2<K, V> peekMin() {
if (!isEmpty()) {
return values.get(0);
}
throw new NoSuchElementException();
}
/**
* Removes the minimum value and returns it
*
* @return a tuple of minimum key and it's weight
*/
public Tuple2<K, V> pollMin() {
if (!isEmpty()) {
Tuple2<K, V> value = values.get(0);
swap(0, values.size() - 1);
values.remove(values.size() - 1);
indexes.remove(value._1);
if (!isEmpty()) {
shiftDown(0);
}
return value;
}
throw new NoSuchElementException();
}
/**
* @return true if the heap is empty
*/
public boolean isEmpty() {
return indexes.isEmpty();
}
/**
* @param key a key to search
*
* @return true if the heap contains the key
*/
public boolean contains(K key) {
return indexes.containsKey(key);
}
/**
* Removes all values from the heap
*/
public void clear() {
values.clear();
indexes.clear();
}
/**
* @return the heap size
*/
public int size() {
return indexes.size();
}
/**
* Puts a key and associated value to the heap
* If there is already a value associated with this key the old value will be overwritten
* The position of the key in the heap will be recalculated with respect of new value
*
* @param key a key to insert
* @param value a weight associated with the key
*/
public void put(K key, V value) {
int idx = indexes.getOrDefault(key, values.size());
indexes.put(key, idx);
if (idx == values.size()) {
values.add(new Tuple2<>(key, value));
} else {
values.set(idx, new Tuple2<>(key, value));
}
shiftUp(idx);
shiftDown(idx);
}
/**
* @param key
*
* @return a weight associated with the key
*/
public V get(K key) {
Integer idx = indexes.get(key);
if (idx == null) {
throw new NoSuchElementException();
}
return values.get(idx)._2;
}
/**
* Validates that the value is greater than it's parent
* If not the value will be swapped with it's parent
* In case if the values were swapped performs recursively for it's new position
* until a parent is less then the value or the top of the heap is reached
*
* @param idx an index in the heap
*
* @return true if values were swapped at least once
*/
private void shiftUp(int idx) {
if (idx != 0) {
int parentIdx = parent(idx);
if (values.get(parentIdx)._2.compareTo(values.get(idx)._2) >= 0) {
swap(idx, parentIdx);
shiftUp(parentIdx);
}
}
}
/**
* Validates that the value is less than both it's children
* If not the value will be swapped with it's the smallest child
* In case if the values were swapped performs recursively for it's new position
* until the value is less then it's children or it becomes a leaf
*
* @param idx an index in the heap
*/
private void shiftDown(int idx) {
int min = idx;
V weight = values.get(idx)._2;
for (int child : children(idx)) {
if (child < values.size()) {
V curr = values.get(child)._2;
if (curr.compareTo(weight) < 0) {
min = child;
weight = curr;
}
}
}
if (min != idx) {
swap(idx, min);
shiftDown(min);
}
}
/**
* Swaps two values in the heap
* Updates their indexes in the index map
*
* @param idx1
* @param idx2
*/
private void swap(int idx1, int idx2) {
Tuple2<K, V> value1 = values.get(idx1);
Tuple2<K, V> value2 = values.get(idx2);
values.set(idx1, value2);
values.set(idx2, value1);
indexes.put(value1._1, idx2);
indexes.put(value2._1, idx1);
}
/**
* @param idx
*
* @return indexes of the children for passed index
*/
private int[] children(int idx) {
int right = (idx + 1) * 2;
int left = right - 1;
return new int[]{left, right};
}
/**
* @param idx
*
* @return the index of node's parent
*/
private int parent(int idx) {
return (idx - 1) / 2;
}
}