[CS][Data Structure] 힙 (Heap)

Heap이란?

Heap은 이진 트리를 기반으로한 자료구조로 부모 노드와 자식 노드 간의 순서 관계를 유지합니다.
Heap은 순서 관계에 따라 최대 힙(Max Heap), 최소 힙(Min Heap) 두 가지로 나눠집니다.

1. 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다. 루트는 항상 최대값이 있습니다.
2. 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다. 루트는 항상 최솟값이 있습니다.

Heap의 기본 연산

1. 삽입 : 새로운 원소를 삽입하는 경우 힙의 속성을 유지하기 위해 트리를 재구성하는 과정이 포함되기 때문에 O(logN)의 시간 복잡도를 가집니다.
2. 삭제 : 노드의 값을 삭제하는 경우 힙의 속성을 유지하기 위해 트리를 재구성하는 과정이 포함되기 때문에 O(logN)의 시간 복잡도를 가집니다.
3. 조회 : 힙의 루트 노드가 항상 최대값 또는 최솟값을 가지기 때문에 O(1)의 시간복잡도를 가집니다.

Heap의 장점

1. 힙은 최대값 또는 최솟값 검색 성능이 뛰어나며 평균 시간 복잡도가 O(logN)입니다.
2. 완전 이진 트리의 구조를 가지기 때문에 배열로 구현 시 메모리 관리가 효율적입니다.
3. 삽입과 삭제 연산이 매우 빠릅니다.

Heap의 단점

1. 임의의 데이터를 검색하는 것에는 효율적이지 않습니다.

Heap의 활용

우선순위 큐

힙의 우선순위에 따라 데이터를 처리하는 자료구조입니다.

힙 정렬

힙을 사용하여 정렬 알고리즘을 구현할 수 있습니다.

다익스트라 

최단 경로 탐색 알고리즘인 다익스트라에서 최소 힙을 사용하여 더 효율적인 처리가 가능합니다.