힙(Heap) :

힙(heap) : 여러 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

힙의 특성

• 완전 이진 트리의 일종
• 반정렬 상태 (느슨한 정렬 상태)
• 힙 트리는 중복된 값 허용된다. (이진 탐색 트리는 허용 X)
• 부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진 트리를 말한다.

힙의 종류

1. 최대 힙(Max Heap)

• 부모 키 값이 자식노드 키 값보다 큰 힙
• Key(parent) ≥ Key(child)
• 가장 큰 값이 루트노드에 있음

2. 최소 힙(Min Heap)

• 부모 키 값이 자식노드 키 값보다 작은 힙
• Key(parent) ≤ Key(child)
• 가장 작은 값이 루트노드에 있음

※ 루트 노드 : 부모 노드가 없이 최상단에 있는 노드를 말한다.

힙의 사용 이유

• 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다.
• 하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.
• 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다.

부모 노드와 자식 노드 관계

왼쪽 자식 index = (부모 index) x 2
오른쪽 자식 index = ((부모 index) x 2) +1
부모 index = (자식 index) / 2

※인덱스 번호 예시

1) 10은 젤 상단 루트 노드이므로 index 번호 = 1
2) 9는 부모 노드 index가 1이고 왼쪽 자식이므로 1X2=2
3) 5는 부모 노드 index가 1이고 오른쪽 자식이므로 (1X2)+1=3
4) 3은 부모노드 index=2에 오른쪽 자식이므로 (2X2)+1=5
5) 6은 부모노드 index가 4에 왼쪽 자식이므로 4X2=8

힙의 동작

1. 데이터 삽입

1) 20을 왼쪽 최하단부 노드에 삽입한다.
2) 20이 3,4보다 크므로 오른쪽 노드에 위치
3) 20의 부모 노드인 8과 비교한다. 20이 더 크므로 8과 위치를 바꾼다.
4) 20의 부모 노드인 15와 비교한다. 20이 더 크므로 15와 위치를 바꾼다.

2. 데이터 삭제

1) 최대값을 갖는 부모 노드를 삭제한다.
2) 부모 노드가 비었으므로, 가장 최하단부 노드를 루트로 옮긴다.
3) 부모 노드인 8보다 값이 큰 자식 노드가 있는지 비교한다.

• 왼쪽, 오른쪽 자식 노드 모두 부모 노드보다 클 경우
  : 왼쪽 자식 노드와 오른쪽 자식 노드를 비교하여, 더 큰 자식 노드와 부모 노드의 위치를 바꾼다.
• 왼쪽, 오른쪽 자식 노드 중 하나만 부모 노드보다 클 경우
  : 둘 중에 부모 노드보다 큰 자식 노드와 부모 노드의 위치를 바꾼다.