[힙] 우선순위 큐 : 힙

힙 (Heap)

• 대표적인 우선순위 큐
• 완전 이진 트리 구조 사용
• 힙에서는 모든 부모 노드가 자식 노드보다 크거나(최대 힙) 혹은 작음(최소 힙)
• 원소를 검색할 수 있는 기능은 필요없고, 우선순위가 가장 높은 것을 알려주고 삭제할 수 있으면 됨
• 사용 예시 : 운영 체제에서 프로세스 스케줄링, 네트워크 트래픽 관리, 시뮬레이션 시스템 등
• 힙과 이진 트리는 모두 계층적 데이터를 저장하고 처리하는 데 유용한 자료구조
• 힙은 주로 우선 순위에 따른 데이터 처리에, 이진 트리(특히 이진 탐색 트리)는 정렬된 데이터의 효율적인 탐색에 사용

 

우선순위 큐 ADT

[핵심 작업]
원소를 삽입한다
최대 원소를 알려주면서 삭제한다
최대 원소를 알려준다
[공통]
우선순위 큐가 비어 있는지 확인한다
우선순위 큐를 깨끗이 비운다

 

 

주요 용어

• 노드(Node): 트리의 기본 단위로, 힙에서 각 노드는 데이터를 포함
• 루트 노드(Root Node): 트리의 최상단에 위치한 노드. 힙에서는 최대 힙의 경우 최댓값, 최소 힙의 경우 최솟값
• 리프 노드(Leaf Node) 또는 말단 노드(Terminal Node): 자식 노드가 없는 노드. 힙에서 리프 노드는 트리의 가장 낮은 레벨에 위치함
• 부모 노드(Parent Node)와 자식 노드(Child Node): 힙에서 각 노드는 최대 두 개의 자식 노드를 가질 수 있으며, 각 자식 노드는 하나의 부모 노드를 가짐
• 레벨(Level): 루트 노드로부터의 거리. 루트 노드는 레벨 0에 위치함

 

우선순위 큐의 작동 원리

• 삽입(Enqueue): 새 요소는 힙의 가장 마지막에 추가된 후, 부모 노드와 비교하면서 올바른 위치로 이동. 이 과정은 우선순위를 유지하기 위해 수행
• 삭제(Dequeue): 힙에서 요소를 삭제할 때는 보통 루트 노드를 삭제. 이후 가장 마지막 요소를 루트로 이동시킨 후, 올바른 위치로 이동시킵니다. 이 과정은 힙 속성을 유지하기 위해 수행

 

힙의 기본 연산

• 힙(Heap)을 조작할 때 사용되는 두 가지 기본 연산
• 요소의 추가와 제거 시에 힙의 속성을 유지함으로써, 우선순위 큐는 항상 올바른 순서로 요소를 처리할 수 있음

 

 

PriorityQueue 클래스와 같은 우선순위 큐 구현체에서는 "스며오르기" (Percolate Up)와 "스며내리기" (Percolate Down)와 같은 연산이 내부적으로 구현되어 있음.


offer() 메소드는 새 요소를 추가하며 내부적으로 "스며오르기"를 수행하고,
poll() 메소드는 요소를 제거하며 내부적으로 "스며내리기"를 수행함.

 

스며오르기 (Percolate Up, Up-Heapify)

• 스며오르기는 새로운 요소가 힙에 추가될 때 사용되는 연산
• 새 요소는 처음에 힙의 말단(즉, 트리의 가장 낮은 레벨의 가장 오른쪽)에 삽입됨
• 그다음 힙의 속성을 만족시키기 위해 위로 "스며오르게" 됨

1. 새 요소를 힙의 말단에 삽입합니다.
2. 삽입된 요소를 그 부모와 비교합니다.
3. 힙의 속성에 따라, 삽입된 요소가 부모보다 우선순위가 높으면(최대 힙에서는 더 크고, 최소 힙에서는 더 작으면), 그 요소를 부모와 교환합니다.
4. 이 과정을 요소가 더 이상 교환되지 않거나 루트에 도달할 때까지 반복합니다.

 

 

스며내리기 (Percolate Down, Down-Heapify)

• 스며내리기는 힙에서 요소를 제거할 때 사용되는 연산
• 힙에서는 보통 루트 요소(최대 힙에서는 최댓값, 최소 힙에서는 최솟값)가 제거됨
• 루트 요소를 제거한 후, 힙의 말단에서 가장 오른쪽에 있는 요소를 루트로 이동시킴
• 이 요소를 "스며내리게" 하여 힙의 속성을 복구함

1. 말단의 가장 오른쪽 요소를 루트로 이동시킵니다.
2. 이 요소와 그 자식들을 비교합니다.
3. 힙의 속성에 따라, 이 요소가 자식들보다 우선순위가 낮으면(최대 힙에서는 더 작고, 최소 힙에서는 더 크면), 가장 우선순위가 높은 자식과 교환합니다.
4. 이 과정을 요소가 더 이상 교환되지 않거나 리프 노드에 도달할 때까지 반복합니다.