힙
완전 이진 트리 기반의 자료구조
‘더미’라는 뜻처럼 데이터들이 느슨하게 정렬된 상태로 쌓여있는 형태
특징
- 항상 최댓값 또는 최솟값을 빠르게 찾을 수 있다.
- 이진 탐색 트리와는 달리 중복 값을 허용한다.
종류
힙은 부모-자식 노드의 대소관계에 따라 두 가지로 나눌 수 있다.
최대 힙
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
부모의 키 값 ≥ 자식 노드의 키 값
최소 힙
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
부모의 키 값 ≤ 자식 노드의 키 값
힙의 구현
힙은 배열을 이용해 구현할 수 있다.
인덱스 계산 규칙
현재 노드 인덱스 =
i
부모 =(i - 1) / 2
왼쪽 자식 =2i + 1
오른쪽 자식 =2i + 2
→ 이 인덱스 계산을 통해 트리를 순회하지 않고도 연관된 노드를 바로 찾아낼 수 있다.
힙의 삽입, 삭제 등의 연산은 일반 이진트리와는 다르게 루트 노드만을 조작하는 것이 아니라, 다른 노드와도 교환하는 과정이 필요하다.
삽입 연산 : Head Up
새로운 요소가 힙의 가장 마지막 위치에 추가된 후, 힙 속성을 만족할 때까지 부모 노드와 비교하며 위로 올라간다.
-
삽입 연산의 과정
삽입 - 새 요소를 배열의 맨 끝에 추가, 완전 이진 트리 구조를 유지
비교 및 교환 - 현재 노드와 부모 노드를 비교. 현재 노드의 값이 부모 노드보다 작다면(최소 힙) / 크다면 (최대힙) 두 노드를 교환
반복 - 루트 노드에 도달하거나 힙 속성을 만족할 때까지 이 과정을 반복
-
구현 예시 (최소 힙)
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class MinHeap {
private List<Integer> heap;
public MinHeap() {
this.heap = new ArrayList<>();
}
// 힙에 새로운 요소를 삽입
public void insert(int value) {
// 1. 배열의 마지막에 요소를 추가
heap.add(value);
// 2. 추가된 위치에서 힙 속성을 맞추기 위해 위로 이동
percolateUp(heap.size() - 1);
}
// 힙 속성을 맞추기 위해 요소를 위로 올리는(Heap Up) 과정
private void percolateUp(int index) {
// 루트 노드(index 0)가 아닐 때까지 반복
while (index > 0) {
int parentIndex = (index - 1) / 2;
// 최소 힙 기준 - 현재 노드가 부모 노드보다 작으면 교환
if (heap.get(parentIndex) > heap.get(index)) {
// Collections.swap을 이용하여 두 요소의 위치를 교환
Collections.swap(heap, parentIndex, index);
index = parentIndex; // 부모 위치로 인덱스 이동
} else {
break; // 힙 속성 만족
}
}
}
}삭제 연산 : Head Down
힙에서 삭제는 항상 루트 노드에서 이루어진다.
-
삭제 연산의 과정
루트 제거 및 대체 - 루트 노드를 삭제하고, 배열의 맨 마지막 요소를 루트로 이동
자식 노드 비교 - 새로운 노드와 그 자식 노드들을 비교. 두 자식 중 더 작은 값(최소 힙) / 더 큰 값 (최대힙)을 가진 자식과 비교
교환 및 반복 - 자식 노드가 현재 노드보다 더 작은 경우(최소 힙) / 큰 경우(최대 힙), 그 자식과 위치를 교환. 힙 속성 만족할 때까지 이 과정을 반복
-
구현 예시 (최소 힙)
// 힙에서 루트 노드(최솟값)를 제거하고 반환
public int remove() {
if (heap.isEmpty()) {
throw new IllegalStateException("Heap is empty");
}
// 1. 루트 노드 (가장 작은 값) 저장
int minVal = heap.get(0);
// 2. 가장 마지막 요소를 루트로 이동 후, 마지막 요소 삭제
int lastIndex = heap.size() - 1;
Collections.swap(heap, 0, lastIndex);
heap.remove(lastIndex);
// 3. 새로운 루트에서 힙 속성을 맞추기 위해 아래로(Percolate Down) 이동
if (!heap.isEmpty()) {
percolateDown(0);
}
return minVal;
}
// 힙 속성을 맞추기 위해 요소를 아래로 내리는(Heap Down) 과정
private void percolateDown(int index) {
int smallest = index;
// 최소 힙의 경우, 자식 노드 중 더 작은 값을 가진 노드를 찾아야 함
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
// 왼쪽 자식이 존재하고 현재 노드보다 작다면 smallest를 왼쪽 자식으로 설정
if (leftChild < heap.size() && heap.get(leftChild) < heap.get(smallest)) {
smallest = leftChild;
}
// 오른쪽 자식이 존재하고 (왼쪽 자식과 비교하여) 현재 smallest보다 작다면 smallest를 오른쪽 자식으로 설정
if (rightChild < heap.size() && heap.get(rightChild) < heap.get(smallest)) {
smallest = rightChild;
}
// 힙 속성이 깨진 경우 (smallest가 현재 인덱스가 아닌 경우)
if (smallest != index) {
Collections.swap(heap, index, smallest);
percolateDown(smallest); // 교환된 위치에서 다시 검사
}
}
}우선순위 큐를 사용하는 방법
자바에서는 PriorityQueue 클래스를 사용해 힙 자료구조를 쉽게 사용할 수 있다.
우선순위 큐는 기본적으로 최소 힙으로 구현되어있다.
import java.util.PriorityQueue;
import java.util.Collections;
// 기본 - 최소 힙
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 최대 힙으로 사용하고 싶을 경우
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 삽입 (O(logN))
minHeap.offer(10);
minHeap.offer(5);
minHeap.offer(20);
// 최소/최대값 확인 (O(1))
int peek = minHeap.peek(); // 5
// 최소/최대값 삭제 및 반환 (O(logN))
int removed = minHeap.poll(); // 5가 삭제되고 반환