이진 힙(Binary Heap)

• 힙의 특징은 Complete Binary Tree 입니다. 즉, 트리에 빈 공간이 생기지 않습니다.
• Complete Binary Tree의 특징은 배열로 만들 수 있다는 점입니다. 이진 힙은 일반적으로 배열로 구현 됩니다.
• 힙은 정렬을 하기 위해 자주 사용 됩니다.
• 힙은 최대 힙과 최소 힙으로 구분 됩니다. 최대 힙은 노드를 모두 제거하면, 내림차순으로 정렬되고, 최소 힙은 노드를 모두 제거하면 오름차순으로 정렬 됩니다.
• 최대 힙은 제일 큰 값이 루트 노드에 오고, 최소 힙은 제일 작은 값이 루트 노드에 옵니다.
• 힙의 서브 트리는 하나의 묶음으로 1과 2 각각 서브트리를 교환해도 똑같이 이진 힙의 성질을 유지합니다.
• 노드를 트리에 관해 삽입, 수정, 삭제 하는 경우 힙이 무너지므로 Heapify 연산을 통해 다시 힙 배열로 바꿔줍니다.
• 삽입 시 실행되는 스왑 연산을 HeapifyUp 이라 하고, 삭제 시 실행되는 연산을 HeapifyDown 이라 부릅니다.
• 이 때, 특정 값을 지닌 노드를 삭제/수정의 경우에는 힙 배열 길이의 절반에서 -1이 되는 지점(length/2-1)의 노드 부터 루트 노드까지 각 자식 노드와 비교하여 자리를 바꿔주는 연산을 반복하는데, 이를 Heapify 연산이라 부릅니다.
  • 참고로 히피파이 연산은 자식이 부모 보다 큰 경우 부모와 자식의 위치를 바꿔주는 연산입니다.
• 힙은 아래와 같은 트리가 되며, 이를 [0, 1, 2, 3, 4, 5, …, 14] 형태의 배열로 간단하게 표시할 수 있습니다.

부모노드의 왼쪽, 오른쪽 자식노드의 인덱스 구하기

• 부모노드의 왼쪽 자식 노드: 2X + 1
• 부모노드의 오른족 자식 노드: 2X + 2

<aside> 💡 여기서 X 는 부모노드의 인덱스를 의미합니다. 강의 학습을 떠나 개인적으로 찾아보니 루트의 인덱스를 1로 설정하는 경우에는 leftChildeIndex = 2X , rightChildIndex = 2X+1 로 두기고 합니다.

</aside>