Heap

Heap (data structure) - Wikipedia

• Heap은 tree 기반의 자료구조로, max heap과 min heap이 있다. max heap은 root node가 항상 최댓값이며 반대로 min heap은 root node가 항상 최솟값이다. 
• Heap은 priority queue ADT(abstrct data type)의 가장 효율적인 구현이라서 종종 priority queue로 언급되기도 한다. 엄격하게 말하자면 priority queue가 더 넓은 범위다.
• Heap은 전체가 정렬된 자료 구조는 아니다. 대신 우선 순위가 가장 높은 개체를 반복적으로 제거하거나 혹은 제거와 삽입을 함께 반복해야하는 경우에 유용하다. (최댓값 혹은 최솟값을 힙에서 가져오는 시간 복잡도는 O(logN)이다.)
• BST(Binary Search Tree)와 다른 점은 Heap은 부분적으로 정렬된 형태지만, BST는 tree 전체가 정렬되어 있다. 크게 Heap은 상하 관계를 보장하고, BST는 좌우 관계를 보장한다고 보면 된다.
• 일반적으로 사용하는 힙은 binary heap이다. 
• Dijstra와 같이 효율적인 그래프 알고리즘에서도 중요하게 쓰인다.

---

구현은 배열로 한다. 이진 트리 기반의 heap은 배열로 표현이 가능하기 때문이다.

 

크게 Insert과 Extraction 두 가지 동작이 존재한다.

Insertion

1. 배열 마지막에 새로운 요소를 추가한다

2. tree 구조이므로 "현재 노드 인덱스 / 2" 가 부모 노드의 인덱스가 된다.

3. 부모 노드와 값을 비교하고 스왑한다.

 

2-3 번 과정을 반복한다. (따라서 시간 복잡도가 O(log N)이 된다.)

 

Extraction

1. 배열 가장 앞에 있는 root node를 뱉는다. 즉 시간 복잡도가 O(1)이다.

2. 배열 가장 뒤에 있는 요소를 root node로 이동시킨다.

3. 자식 노드들과 비교하여 최소 혹은 최댓값을 찾을 때까지 스왑한다.

 

추출은 O(1)이지만, 다시 힙을 정렬하는 과정에서 O(log N)의 시간복잡도를 가지게 된다.

즉 추출과 삽입 모두 O(log N)의 시간복잡도가 소요된다.

---