히프(heap) 개념
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리
- 여러 개의 값들 중 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조
- 히프 트리에서는 중복된 값을 허용(완전 이진 트리에서는 허용 x)
- "느슨한 정렬 상태 유지": 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도
- 삭제 연산마다 가장 큰 값을 찾아내기만 하면 되므로 완전히 정렬할 필요 x
- 히프는 완전 이진 트리
히프의 종류
- 2가지의 히프 트리 존재
1. 최대 히프(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- key(부모 노드) ≥ key(자식 노드)
2. 최소 히프(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- key(부모 노드) ≤ key(자식 노드)
히프의 구현
- 히프는 완전 이진 트리이므로 각각의 노드에 번호를 붙일 수 있음
- 이 번호를 배열의 인덱스로 생각하고 배열을 이용해 히프 구현 가능(편의를 위해 인덱스 0 사용 x)
- 배열을 이용해 히프를 저장하면 자식 노드와 부모 노드를 쉽게 알 수 있음
- 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2+!1
- 부모의 인덱스 = (자식의 인덱스)/2
