[자료구조] Heap

힙의 삽입 연산

1. 힙의 최고 깊이 가장 우측 노드에 새 노드를 추가 ( 이때 힙은 완전 이진 트리 유지)

1. 삽입한 노드가 부모 노드보다 작다면 부모노드와 위치를 서로 바꿈 → 2단계를 다시 진행

힙의 최소값 삭제 연산

1. 힙의 최고 깊이에 있던 노드를 루트 노드로 옮겨야 한다 ( 이때 힙 순서 속성이 파괴 , 이를 복원하는 과정 진행)

1. 옮겨온 노드의 양쪽 자식을 비교하여 작은 쪽 자식과 위치를 교환 → 힙 순서 속성을 지키려면 부모 노드 양쪽 자식보다 작은 값을 가져야 하기 때문

1. 옮겨온 노드가 더 이상의 자식이 없는 리프 노드로 되거나 양쪽 자식보다 작은 값을 갖는 경우 삭제 연산을 종료 , 그렇지 않다면 다시 2단계를 반복

힙의 구현

• 깊이 0의 노드는 배열의 0인덱스

• 깊이 1의 노드는 배열의 1~2인덱스

• 깊이 2의 노드는 배열의 3~6인덱스

• 깊이 n의 노드는 배열의 2^n-1 ~ 2^(n+1)-2 요소 인덱스에 저장된다

• 왼쪽 자식 노드 : 2k+1

• 오른쪽 자식 노드 : 2k+2

• 부모 노드는 : 2k-1 / 2