힙(Heap)

힙 - 데이터에서 최대,최소를 빠르게 찾기 위해 생긴 이진트리

• 완전 이진트리 - 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

힙 사용하는 이유

• 빠르게 찾기 위해 배열은 시간 복잡도 O(n) 힙 같은 경우는 O(logn)임

힙의 구조

• 힙은 최대값을 구하기 위한 구조와 최소값을 구하기 위한 구조로 분류한다
• 각 노드의 값은 자식 노드가 가진 값보다 크거나 같다(최대힙)
• 최소 힙의 경우는 각 노드의 값이 해당 노드의 자식 노드가 가진 값보다 크거나 작다
• 완전 이진트리 형태를 가진다

이진트리와 힙의 공통점 및 차이점

• 공통점 : 이진트리 형태로 구성되어있다.
• 차이점

1. 힙은 각 노드의 값이 자식 노드보다 크거나 같다(최대힙)
2. 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그다음 부모, 그다음 오른쪽 노드값이 가장 크다
3. 힙은 자식 노드에서 작은값은 왼쪽 큰값은 오른쪽 이라는 조건이 없다.
4. 이진 트리는 탐색을 위해 힙은 최대 최소를 구하기 위해 사용한다고 생각하면 된다.

힙의 구현

• 힙은 배열 자료구조로 구현한다. 하지만 인덱스가 0부터 시작하기 때문에 1로 맞춰줘야한다.
• 부모 노드 인덱스 번호 = 자식노드 인덱스 번호 / 2
• 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
• 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1