힙 (Heap)
- 힙은 힙의 특성을 만족하는 완전 이진 트리로, 최소 힙 기준으로 각 노드의 원소는 항상 자식 노드의 원소보다 작거나 같아야 한다.
- 최소 힙의 부모 노드는 항상 자식 노드보다 크거나 같지만, 부모-자식 간의 관계만 정의되어 있을 뿐 좌우 관계에 대한 정의는 하지 않기 때문에 힙은 정렬된 구조는 아니다.
인덱스
- 완전 이진 트리 형태인 이진 힙은 배열에 빈틈없이 배치가 가능하며, 대개 트리의 배열 표현의 경우 계산의 편의성을 위해 0번째 인덱스는 비워두고 1번째 인덱스부터 사용한다.
- i번째 노드에 대해 부모 노드의 인덱스는 i // 2, 왼쪽 자식 노드의 인덱스는 2 * i, 오른쪽 자식 노드의 인덱스는 2 * i + 1로 계산된다.
원소 삽입 (Python)
- 최소 힙에 원소를 삽입할 때는 언제나 트리의 밑바닥의 가장 오른쪽 위치에 삽입된다.
- 이후 새로 삽입된 원소가 힙의 특성을 만족하는 자리를 찾을 때까지 부모 노드와 교환해 나간다. (Up Heap)
- 힙에 있는 노드의 개수를 N이라고 할 때, 삽입에 걸리는 시간 복잡도는 O(logN)이다.
def percolate_up(q):
i = len(q)
parent = i // 2
while parent >= 0:
if q[i] < q[parent]:
q[i], q[parent] = q[parent], q[i]
i = parent
parent = i // 2
최소 원소 추출 (Python)
- 최소 원소, 즉 루트 노드를 제거한 후 트리의 밑바닥의 가장 왼쪽에 위치한 원소로 대체한다.
- 그 다음 최소 힙의 성질을 만족하도록 해당 노드를 자식 노드와 교환해 나감으로써 밑으로 보낸다. (Down Heap)
- 루트를 추출한 이후 다시 힙의 특성을 유지하는 작업이 필요하기 때문에 시간 복잡도는 O(logN)이다.
def heapfify(idx):
left = idx * 2
right = idx * 2 + 1
parent = idx
if left < len(q) and q[left] > q[parent]:
parent = left
if right < len(q) and q[right] > q[parent]:
parent = right
if parent != idx:
q[idx], q[parent] = a[parent], a[idx]
heapfify(parent)
힙 VS 이진 탐색 트리
- 힙은 상하 관계를 보장하며, 특히 최소 힙에서는 부모가 항상 자식보다 작다.
- 힙은 가장 큰 값을 추출하거나 가장 작은 값을 추출하는 것과 같이 우선순위와 연관되어 있다.
- 반면에 BST는 좌우 관계를 보장하는데, 부모는 왼쪽 자식보다는 크며 오른쪽 자식보다는 작거나 같다.
- 이러한 특징으로 인해 BST는 탐색과 삽입 모두 O(logN)에 가능하며, 모든 값이 정렬되어야 할 때 사용한다.
힙 구현 (JAVA)
import java.util.Comparator;
import java.util.NoSuchElementException;
public class Heap<E> {
private final Comparator<? super E> comparator;
private static final int DEFAULT_CAPACITY = 10;
private int size;
private Object[] arr;
public Heap() {
this(null);
}
public Heap(Comparator<? super E> comparator) {
this.arr = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
public Heap(int capacity) {
this(capacity, null);
}
public Heap(int capacity, Comparator<? super E> comparator) {
this.arr = new Object[capacity];
this.size = 0;
this.comparator = comparator;
}
// 부모 노드 인덱스 반환
private int getParentIdx(int index) {
return index / 2;
}
// 왼쪽 자식 노드 인덱스 반환
private int getLeftChildIdx(int index) {
return index * 2;
}
// 오른쪽 자식 노드 인덱스 반환
private int getRightChildIdx(int index) {
return index * 2 + 1;
}
private void resize(int newCapacity) {
Object[] newArr = new Object[newCapacity];
for (int i = 1; i <= size; i++) {
newArr[i] = arr[i];
}
this.arr = newArr;
}
public void insert(E value) {
if (size + 1 == arr.length) {
resize(arr.length * 2);
}
// 추가될 위치와 넣을 값을 넘겨준다.
shiftUp(size + 1, value);
size++;
}
private void shiftUp(int index, E target) {
if (comparator != null) {
shiftUpComparator(index, target, comparator);
}
else
shiftUpComparable(index, target);
}
@SuppressWarnings("unchecked")
private void shiftUpComparator(int index, E target, Comparator<? super E> comparator) {
while (index > 1) {
int parent = getParentIdx(index);
Object parentVal = arr[parent];
// 타겟 노드 값이 부모노드보다 크면 반복문 종료
if (comparator.compare(target, (E) parentVal) >= 0) {
break;
}
// 부모 노드와 현재 노드를 바꾼다.
arr[index] = parentVal;
index = parent;
}
// 최종 위치에 타겟 노드값 저장
arr[index] = target;
}
@SuppressWarnings("unchecked")
public void shiftUpComparable(int index, E target) {
Comparable<? super E> comparable = (Comparable<? super E>) target;
while (index > 1) {
int parentIdx = getParentIdx(index);
Object parentVal = arr[parentIdx];
if (comparable.compareTo((E) parentVal) >= 0) {
break;
}
arr[index] = parentVal;
index = parentIdx;
}
arr[index] = target;
}
@SuppressWarnings("unchecked")
public E getMin() {
if (arr[1] == null) {
throw new NoSuchElementException();
}
E result = (E) arr[1];
E target = (E) arr[size];
arr[size] = null;
// 루트 노드의 인덱스와 재배치할 타겟 노드를 넘겨준다.
shiftDown(1, target);
return result;
}
public void shiftDown(int index, E target) {
if (comparator != null) {
shiftDownComparator(index, target, comparator);
}
else {
shiftDownComparable(index, target);
}
}
@SuppressWarnings("unchecked")
private void shiftDownComparator(int index, E target, Comparator<? super E> comparator) {
arr[index] = null;
size--;
int parent = index;
int child;
// 왼쪽 자식 노드의 인덱스가 요소의 개수보다 작을때까지 반복
while ((child = getLeftChildIdx(parent)) <= size) {
int right = getRightChildIdx(parent);
Object childVal = arr[child];
// 오른쪽 자식 인덱스가 size를 넘지 않으면서, 왼쪽 자식이 오른쪽 자식보다 큰 경우
// 자식 노드를 오른쪽 자식 노드로 바꿔준다.
if (right <= size && comparator.compare((E) childVal, (E) arr[right]) > 0) {
child = right;
childVal = arr[child];
}
// 타겟 노드가 자식 노드보다 작을 경우 반복문 종료
if (comparator.compare(target, (E) childVal) <= 0) {
break;
}
// 부모 노드와 자식 노드를 바꾼다.
arr[parent] = childVal;
parent = child;
}
// 최종 위치에 타겟값을 넣어준다.
arr[parent] = target;
if (arr.length > DEFAULT_CAPACITY && size < arr.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, arr.length / 2));
}
}
@SuppressWarnings("unchecked")
private void shiftDownComparable(int index, E target) {
Comparable<? super E> comparable = (Comparable<? super E>) target;
arr[index] = null;
size--;
int parentIdx = index;
int childIdx;
while((childIdx = getLeftChildIdx(parentIdx)) <= size) {
int rightIdx = getRightChildIdx(parentIdx);
Object childVal = arr[childIdx];
if(rightIdx <= size && ((Comparable<? super E>)childVal).compareTo((E)arr[rightIdx]) > 0) {
childIdx = rightIdx;
childVal = arr[childIdx];
}
if(comparable.compareTo((E) childVal) <= 0){
break;
}
arr[parentIdx] = childVal;
parentIdx = childIdx;
}
arr[parentIdx] = target;
if(arr.length > DEFAULT_CAPACITY && size < arr.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, arr.length / 2));
}
}
}
우선순위 큐
- 어떠한 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형으로, 최단 경로를 탐색하는 다익스트라 알고리즘에 활용된다.
- 파이썬에서 사용한은 heapq 모듈은 내부적으로 힙으로 구현되어 있다.
'Python > Algorithm' 카테고리의 다른 글
버블 정렬, 선택 정렬, 삽입 정렬 (0) | 2022.03.01 |
---|---|
트라이 (0) | 2022.02.27 |
트리의 종류와 트리 순회 (0) | 2022.02.26 |
최단 경로 알고리즘 (0) | 2022.02.25 |
그래프와 그래프 탐색 (0) | 2022.02.25 |