[CS] 힙

힙 (Heap)

완전 이진 트리 형태의 자료구조

일반적으로 그룹을 정렬하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다.
또한, 우선순위 큐를 구현할 때에도 힙 자료구조를 사용한다.
데이터의 삽입과 삭제가 빠르며 각각의 수행시간은 \(O(logN)\) 이다.

출처 : https://wonit.tistory.com/203

• 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.
• 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다.

 

힙의 삽입 연산

출처 : https://baeharam.github.io/posts/data-structure/heap/

1. 트리의 가장 마지막 위치에 노드를 삽입한다. 
2. 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.
3. 만족하지 않다면 부모와 자식의 키 값을 바꾼다.
4. 조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2번~3번을 반복한다.       

 

힙의 삭제 연산

출처 : https://baeharam.github.io/posts/data-structure/heap/

1. 힙의 삭제 연산은 항상 루트 노드를 삭제한다.
2. 트리의 가장 마지막 노드를 루트 자리로 삽입한다.
3. 바꾼 위치의 노드와 그 자식 노드가 힙 조건을 만족하는지 확인한다.
4. 만족하지 않다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꾼다.
5. 조건을 만족하거나 리프 노드에 도달할 때까지 3번~4번을 반복한다.