[자료구조] 힙

힙은 완전 이진트리로 구현된다. 우선순위 큐를 구현할때 힙을 사용한다.

이진 탐색 트리와 다르게 중복 값을 허용한다.

최소, 최대값만 루트 노드에 있고 그 외엔 큰 값이 상위레벨, 작은 값이 하위레벨에 있다는 정도의 반 정렬 상태를 유지한다.

pop 호출시 항상 루트노드가 제거되고 최소, 최대값이 나오게 된다.

삽입과 삭제에 시행되는 재정렬 과정이 O(NlogN) 이기 때문에 O(NlogN)을 보장한다.

보통 배열을 사용한다.

 

힙의 삽입 (최소힙 기준)

 

1. 힙에 새로운 요소가 들어오면 마지막 노드에 어어서 삽입한다

2. 부모 노드보다 값이 작으면 서로 바꾼다.

3. 2번이 수행되지 않을때까지 루트노드로 올라가며 반복한다.

 

힙의 삭제 (최소힙 기준)

 

1. 루트 노드를 삭제 한다. (가장 끝의 리프노드와 값 교환후, pop)

2. 둘 중 작은값을 가진 자식과 위치 교환

3. 조건을 만족하지 않거나 리프노드가 될 때까지 2번을 반복한다.