1. 힙 (Heap)
- 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)
- 완전 이진 트리 : 노드를 삽일할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
힙 사용 이유
- 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
- 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)
- 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용
2. 힙 (Heap) 구조
- 힙은 최대값을 구하기 위한 구조 (최대힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소힙, Min Heap) 로 분류
- 힙은 다음과 같은 조건을 가지고 있는 자료구조임
- 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대힙의 경우)
- 최소힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같다.
- 완전 이진 트리 형태를 가짐
3. 힙과 이진 탐색 트리의 공통점과 차이점
공통점
- 이진 트리임
차이점
- 힙은 각 노드의 값이 자식 노드보다 크거나 같음 (최대힙의 경우)
- 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고 그 다음 부모 노드 그 다음 오른쪽 자식 노드 값이 가장 큼
- 힙은 이진 탐색 트리의 조건이 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
- 힙의 왼쪽 밑 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해
4. 힙 (Heap) 구현
- 배열 이용해서 데이터를 힙 구조에 삽입, 삭제
- root 노드 인덱스 번호를 1로 지정하면 수월함
- 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 / 2
- 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
- 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1
public class Heap {
private ArrayList<Integer> heap;
public init() {
heap = new ArrayList<Integer>();
heap.add(0); // 0번째 인덱스 사용 안함
}
public Boolean moveUp(Integer index) {
if (index <= 1) {
return false;
}
Integer parentIndex = index / 2;
if (heap.get(index) > heap.get(parentIndex)) {
return true;
} else {
return false;
}
}
public Boolean insert(Integer data) {
if (heap.size() == 0) {
init();
return true;
}
heap.add(data);
Integer index = heap.size() - 1;
while (this.moveUp(index)) {
Integer parentIndex = index / 2;
Integer parentData = heap.get(parentIndex); // 부모 노드의 값
heap.set(parentIndex, data);
heap.set(index, parentData);
index = parentIndex;
}
return true;
}
public Boolean moveDown(Integer index) {
Integer leftChildIndex = index * 2;
Integer rightChildIndex = index * 2 + 1;
if (leftChildIndex >= heap.size()) { // 1. 왼쪽 자식 노드도 없을 때
return false;
} else if (rightChildIndex >= heap.size()) { // 2. 오른쪽 자식 노드만 없을 때
if (heap.get(index) < heap.get(leftChildIndex)) {
return true;
} else {
return false;
}
} else { // 3. 왼쪽, 오른쪽 자식 노드 모두 있을 때
if (heap.get(leftChildIndex) > heap.get(rightChildIndex)) {
if (heap.get(index) < heap.get(leftChildIndex)) {
return true;
} else {
return false;
}
} else {
if (heap.get(index) < heap.get(rightChildIndex)) {
return true;
} else {
return false;
}
}
}
}
public Integer pop() {
if (heap.size() <= 1) {
return null;
}
Integer popData = heap.get(1);
heap.set(1, heap.get(heap.size() - 1);
heap.remove(heap.size() - 1);
Integer index = 1;
while (this.moveDown(index)) {
Integer leftChildIndex = index * 2;
Integer rightChildIndex = index * 2 + 1;
if (rightChildIndex >= heap.size()) { // 2. 오른쪽 자식 노드만 없을 때
if (heap.get(index) < heap.get(leftChildIndex)) {
Integer leftChildData = heap.get(leftChildIndex);
heap.set(leftChildIndex, heap.get(index));
heap.set(index, leftChildData);
}
} else { // 3. 왼쪽, 오른쪽 자식 노드 모두 있을 때
if (heap.get(leftChildIndex) > heap.get(rightChildIndex)) {
if (heap.get(index) < heap.get(leftChildIndex)) {
Integer leftChildData = heap.get(leftChildIndex);
heap.set(leftChildIndex, heap.get(index));
heap.set(index, leftChildData);
}
} else {
if (heap.get(index) < heap.get(rightChildIndex)) {
Integer rightChildData = heap.get(rightChildIndex);
heap.set(rightChildIndex, heap.get(index));
heap.set(index, rightChildData);
}
}
}
}
return popData;
}
public
}
5. 힙 (Heap) 시간 복잡도
- O(logn)
