데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 “완전 이진 트리”
왼쪽 자식 노드 부터 채워지며, 마지막 레벨을 제외한 모든 자식 노드가 채워져 있는 트리
최대 힙 : 내 자식 노드의 값은 내 값보다 작거나 같아야 한다.
최소 힙: 내 자식 노드의 값은 내 값보다 크거나 같아야 한다.
BST 와 달리 내 왼쪽 자식, 오른쪽 자식 간의 크기는 상관 없다.
위 특징들 때문에 최대 힙의 루트 노드는 항상 최대값이 되고
최소 힙의 루트 노드는 항상 최소값이 된다.
힙은 완전 이진 트리이기 때문에 무조건 왼쪽 자식 노드부터 차례차례 채워진다.
따라서 노드가 생성되는 순서가 배열의 append와 같기 때문에
배열로 구현한다.
부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 / 2
왼쪽 자식 노드 인덱스 번호 = (부모 노드 인덱스 번호) * 2
오른쪽 자식 노드 인덱스 번호 = (부모 노드 인덱스 번호 * 2) + 1
struct Heap<T: Comparable> {
var heap : Array<T> = []
init() {}
init (data : T) {
heap.append(data) // 0번 인덱스
heap.append(data) // 실제 root node 채우기
}
}