데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 “완전 이진 트리”

완전 이진 트리

왼쪽 자식 노드 부터 채워지며, 마지막 레벨을 제외한 모든 자식 노드가 채워져 있는 트리

최대 힙 , 최소 힙

최대 힙 : 내 자식 노드의 값은 내 값보다 작거나 같아야 한다.

최소 힙: 내 자식 노드의 값은 내 값보다 크거나 같아야 한다.

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 채우기
		}
}

삽입