힙 트리

여러 개의 값 중 가장 크거나 작은 값을 빠르게 찾기 위한 완전 이진 트리 형식의 트리로 부모 노드의 값이 항상 자식 노드의 값보다 크거나 작도록 만들어 대소관계를 가지도록 만든다. 따라서 루트 노드는 항상 가장 크거나 가장 작은 값을 가지게되며 최댓값(또는 최솟값)을 바로 찾을 수 있게 된다.( O(1) )

 

 * 루트 노드가 가장 클 때는 최대힙, 가장 작을 때는 최소힙이라고 한다.

 

노드 간 값의 대소관계는 오로지 부모 노드와 자식 노드 사이에만 성립하며 형제 노드 사이에서는 관계없다.

즉 아래와 같은 트리가 있으면 A와 B(혹은 C) 간에는 대소관계가 성립되어야 하며 B와 C 간에는 성립되지 않아도 된다.

  A
 / ＼
B   C

 

노드 추가 방법

1. 트리의 가장 마지막에 노드 추가
2. 추가한 노드와 추가한 노드의 부모 노드를 비교
3. 비교한 값이 최대힙(또는 최소힙)의 규칙에 맞지 않으면 부모 노드와 교환
4. 힙 트리의 조건을 만족시키기 위해 상위 노드로 이동하며 루트 노드까지 비교 및 교환

 

노드 삭제 방법

1. 루트 노드 제거
2. 빈 루트 노드로 마지막 노드를 이동
3. 이동시킨 노드와 해당 노드의 자식 노드를 비교
4. 비교한 값이 최대힙(또는 최소힙)의 규칙에 맞지 않으면 자식 노드와 교환
5. 힙 트리의 조건을 만족시키기 위해 하위 노드로 이동하며 부모 자식 관계를 비교 및 교환

 

노드의 추가와 삭제의 시간복잡도는 모두 O(log N)이 소요된다.