[자료구조] 힙 (Heap)

1. 특징

데이터에서 최댓값/최솟값을 빠르게 찾을 수 있는 완전 이진 트리 (complet binary tree)
완전 이진 트리란? 노드를 삽입할 때 최하단 왼쪽 노드부터 채워지는 트리 
최댓값과 최솟값의 시간복잡도, 데이터 삭제 및 삽입의 시간복잡도는 $O(logn)$ (depth가 한 단계씩 내려가면서 체크횟수를 1/2로 줄여주기 때문)
값의 중복을 허용함
좌/우 노드 간 값의 크기는 상관 없음

2. 구조

최대 힙 Max heap  / 최소 힙 Min heap 
최대 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 (최소 힙은 반대 - 자식 노드보다 부모 노드의 값이 항상 같거나 더 작다) → 최댓값은 탐색할 필요도 없이 root node\

출처:t.ly/xgVE

3. 힙& 이진 탐색 트리의 비교

공통점

모두 이진트리

차이점

이진 탐색 트리는 왼쪽 자식 노드<부모노드<오른쪽 자식 노드 순서로 값이 커짐 - 탐색을 위한 구조 
(In case of max heap) 힙은 각 노드의 값이 자식 노드보다 크거나 같음 - 최댓값&최솟값 검색을 위한 구조 중 하나

4. 구현 (on github)

힙은 완전 이진 트리이기 때문에, 일반적으로 힙 구현시 배열 자료구조를 활용합니다. 
힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월합니다. parent node& child node의 인덱스를 수식으로 표현이 가능하기 때문입니다. 

• 부모 노드 인덱스 번호 (parent node's index) == 자식 노드 인덱스 번호 (child node's index) // 2
• 왼쪽 자식 노드 인덱스 번호 (left child node's index) == 부모 노드 인덱스 번호 (parent node's index) * 2
• 오른쪽 자식 노드 인덱스 번호 (right child node's index) == 부모 노드 인덱스 번호 (parent node's index) * 2 + 1

힙 구현 단계 
1) 완전 이진 트리의 순서에 맞추어 data 추가
2) 추가된 데이터의 값에 따라 데이터의 위치 변경

힙의 데이터 삭제 구현
1) 최상단의 최대 혹은 최솟값을 꺼냄
2) root node가 비지 않도록 구조 변경