heap : 최소 heap, 최대 heaps 로 구성 상위 노드가 하위 노드보다 작거나 크다.
heap(최대)구성
1
2
3
4
5
6
7
8
public class Heap {
public List<Integer> heaps;
public Heap() {
this.heaps = new ArrayList<>();
}
}
구현 메소드
1
2
3
4
5
6
7
void swap(int index1, int index2);
int leftIndex(int index);
int rightIndex(int index);
int parentIndex(int index);
void insert(int value);
Integer remove();
void sinkDown(int index);
void swap(int index1, int index2) : 노드의 순서를 바꾸는 도우미 메소드
1
2
3
4
5
public void swap(int index1, int index2) {
int temp = heaps.get(index1);
heaps.set(index1, heaps.get(index2));
heaps.set(index2, temp);
}
int leftIndex(int index), int rightIndex(int index), int parentIndex(int index) : 노드의 인덱스를 가져오는 도우미 메소드
1
2
3
4
5
6
7
8
9
10
11
public int leftIndex(int index) {
return (2 * index) + 1;
}
public int rightIndex(int index) {
return (2 * index) + 2;
}
public int parentIndex(int index) {
return (index - 1) / 2;
}
void insert(int value)
1
2
3
4
5
6
7
8
9
10
11
public void insert(int value) {
heaps.add(value);
int current = heaps.size() - 1;
while (current > 0 && heaps.get(current) > heaps.get(parentIndex(current))) {
int temp = parentIndex(current);
if (heaps.get(temp) < heaps.get(current)) {
swap(current, parentIndex(current));
current = parentIndex(current);
}
}
}
Integer remove()
1
2
3
4
5
6
7
8
9
10
public Integer remove() {
if (heaps.isEmpty()) return null;
if (heaps.size() == 1) return heaps.get(0);
int answer = heaps.get(0);
int current = heaps.size() - 1;
heaps.set(0, heaps.get(current)); // 마지막 노드와 바꾼다.
heaps.remove(current);
sinkDown(0);
return answer;
}
void sinkDown(int index) : 노드 삭제후 재배열 해주는 도우미 메소드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void sinkDown(int index) {
int maxIndex = index;
while (true) {
int leftIndex = leftIndex(index);
int rightIndex = rightIndex(index);
if (leftIndex < heaps.size() && heaps.get(maxIndex) < heaps.get(leftIndex)) {
maxIndex = leftIndex;
}
if (leftIndex < heaps.size() && heaps.get(maxIndex) < heaps.get(rightIndex)) {
maxIndex = rightIndex;
}
if (maxIndex != index) {
swap(maxIndex, index);
index = maxIndex;
} else {
return;
}
}
}