1. 힙
데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다.
- 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
즉, 힙을 이해하기 위해서는 트리에 대한 사전 지식이 필요하다.
힙은 왜 사용할까?
- 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림,
- 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $ O(log n) $ 이 걸림,
- 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨
1.1. 힙 구조
힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap)로 분류할 수 있다. 즉, 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조이다.
- 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
- 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
- 완전 이진 트리 형태를 가진다.
1.2. 힙과 이진탐색트리의 공통점과 차이점
공통점
- 힙과 이진 탐색 트리는 모두 이진 트리임
차이점
- 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
- 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
- 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
- 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
- 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨
1.3. 힙 동작
힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입한다.
기본 구조
힙에 데이터 삽입하기
- 삽입할 데이터가 힙의 데이터보다 클 경우 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워진다.
힙 데이터 삭제
- 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임
- 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임
- 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동
- root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함 (swap)
1.4. 힙 구현
힙 인터페이스 구현
<code />
public interface IHeap<T> {
void insert(T val);
boolean contains(T val);
T pop();
T peek();
int size();
}
- 힙 구현
<code />
public class MaxHeap<T extends Comparable<T>> implements IHeap<T> {
T[] data;
int size;
int maxSize;
public MaxHeap(int maxSize) {
this.maxSize = maxSize;
this.data = (T[]) new Comparable[maxSize + 1];
this.size = 0;
}
private int parent(int pos) {
return pos / 2;
}
private int leftChild(int pos) {
return (2 * pos);
}
private int rightChild(int pos) {
return (2 * pos) + 1;
}
private boolean isLeaf(int pos) {
return (pos > (size / 2) && pos <= size);
}
private void heapify(int idx) {
if (isLeaf(idx)) {
return;
}
T current = this.data[idx];
T left = this.data[leftChild(idx)];
T right = this.data[rightChild(idx)];
if (current == null) {
return;
}
if (current.compareTo(left) < 0 ||
current.compareTo(right) < 0) {
if (left.compareTo(right) > 0) {
Collections.swap(Arrays.asList(this.data), idx, leftChild(idx));
heapify(leftChild(idx));
} else {
Collections.swap(Arrays.asList(this.data), idx, rightChild(idx));
heapify(rightChild(idx));
}
}
}
@Override
public void insert(T val) {
this.data[++this.size] = val;
int current = this.size;
while (this.data[parent(current)] != null &&
this.data[current].compareTo(this.data[parent(current)]) > 0) {
Collections.swap(Arrays.asList(this.data), current, parent(current));
current = parent(current);
}
}
@Override
public boolean contains(T val) {
for (int i = 1; i <= this.size; i++) {
if (val.equals(this.data[i])) {
return true;
}
}
return false;
}
@Override
public T pop() {
T top = this.data[1];
this.data[1] = this.data[this.size--];
heapify(1);
return top;
}
@Override
public T peek() {
if (this.size < 1) {
throw new RuntimeException();
}
return this.data[1];
}
@Override
public int size() {
return this.size;
}
}반응형
