Priority Queue & Heap

Priority Queue (우선순위 큐)

우선순위 큐는 각 요소에 우선순위를 부여하여, 우선순위가 높은 요소가 먼저 처리되는 큐이다. 일반적인 큐는 FIFO(First-In, First-Out) 방식으로 작동하지만, 우선순위 큐는 우선순위에 따라 처리 순서가 결정된다.

구현

• 배열: 정렬된 배열이나 정렬되지 않은 배열로 구현할 수 있지만, 삽입과 삭제의 효율성에 따라 성능 차이가 있다.
• 연결 리스트: 정렬된 연결 리스트로 구현하면, 삽입은 더 복잡하지만 삭제는 간단해진다.
• 힙(Heap): 가장 효율적인 구현 중 하나로, 우선순위 큐의 삽입과 삭제를 로그 시간 복잡도로 처리할 수 있다.

주요 동작

• Insert: 새로운 요소를 큐에 추가하면서 우선순위를 고려하여 적절한 위치에 배치한다.
• Delete (Extract): 우선순위가 가장 높은 요소를 큐에서 제거하고 반환한다.
• Peek: 우선순위가 가장 높은 요소를 큐에서 제거하지 않고 반환한다.

 

Heap (힙)

힙은 이진트리 기반의 자료구조로, 우선순위큐를 구현한다. 힙은 완전 이진트리로 구성되며, 부모 노드와 자식 노드 간의 관계에 따라 Max Heap과 Min Heap으로 구분된다.

종류

• Max Heap: 부모 노드의 키가 자식 노드의 키보다 크거나 같은 구조이다. 루트 노드에는 가장 큰 키가 위치한다.
• Min Heap: 부모 노드의 키가 자식 노드의 키보다 작거나 같은 구조이다. 루트 노드에는 가장 작은 키가 위치한다.

주요 동작

• Insert: 새로운 요소를 힙에 추가하고, 힙의 성질을 유지하기 위해 적절한 위치로 조정한다.
• Delete (Extract): 루트 노드를 제거하고, 트리의 가장 마지막 노드를 루트로 옮긴 후, 힙의 성질을 유지하도록 재조정한다.
• Peek: 루트 노드를 반환하지만, 힙에서 제거하지 않는다.

Insert 동작 방식

1. 노드 추가: 새로운 요소를 트리의 마지막 위치에 삽입한다.
2. 힙 성질 유지: 삽입된 노드가 부모 노드와 비교되어야 하며, 필요에 따라 위치를 변경해 힙의 특성을 유지한다. 이 과정은 상향식(heapify-up) 또는 bubble-up으로 불린다.

Delete 동작 방식

1. 루트 노드 제거: 루트 노드를 제거하여 가장 큰(혹은 작은) 값을 반환한다.
2. 트리 재구성: 트리의 마지막 노드를 루트로 이동시켜 완전 이진트리의 구조를 유지한다.
3. 힙 성질 유지: 새로운 루트 노드가 자식 노드들과 비교되며, 필요에 따라 위치를 변경해 힙의 특성을 유지한다. 이 과정은 하향식(heapify-down) 또는 bubble-down으로 불린다.

사용 사례

• 프로세스 스케줄링: 운영 체제에서 프로세스의 우선순위에 따라 CPU 자원을 할당할 때 사용된다.
• 힙 정렬: 힙을 사용하여 정렬을 수행하는 알고리즘이다.
• 다익스트라 알고리즘: 그래프에서 최단 경로를 찾는 알고리즘에서 우선순위 큐로 힙을 사용하여 효율적으로 경로를 탐색한다.
• 힙 메모리: 운영 체제의 힙 메모리 영역은 자료 구조 힙과는 별개이며, 동적 메모리 할당을 관리하는 공간이다.