힙과 우선순위 큐

Cheatsheet Content

### 우선순위 큐 (Priority Queue) ADT 우선순위 큐는 요소들을 우선순위에 따라 저장하는 데이터 구조입니다. 삽입은 임의로 이루어지지만, 제거는 우선순위 순서대로 이루어집니다. #### 주요 메서드 - `insert(PQ, x)`: 항목 `x`를 우선순위 큐에 삽입합니다. - `remove_min(PQ)`: 가장 작은(최고 우선순위) 항목을 제거하고 반환합니다. #### 추가 메서드 - `size(PQ)`: 우선순위 큐의 요소 수를 반환합니다. - `pq_empty(PQ)`: 우선순위 큐가 비어있는지 테스트합니다. - `pq_new()`: 새 우선순위 큐를 생성합니다. - `min(PQ)`: 가장 작은(최고 우선순위) 항목을 제거하지 않고 반환합니다. #### 응용 분야 - 주식 시장 - 할 일 목록 - 실시간 시스템 스케줄링 (예: 프로세스 스케줄링) #### 키의 필수 속성 (Required Properties for Keys) - **전체 순서 (Total Ordering)**: 모든 키 쌍에 대해 비교 규칙이 정의되어야 합니다. - **반사성 (Reflexive)**: $x \le x$ - **반대칭성 (Antisymmetric)**: $x \le y \land y \le x \implies x = y$ - **전이성 (Transitive)**: $x \le y \land y \le z \implies x \le z$ - 항목은 일반적으로 (키, 값) 쌍으로 구성되며, 키가 우선순위를 나타냅니다. #### 리스트를 이용한 구현 비교 | 연산 | 정렬되지 않은 리스트 | 정렬된 리스트 | |--------------|--------------------|--------------| | `size`, `empty` | $O(1)$ | $O(1)$ | | `insert` | $O(1)$ | $O(n)$ | | `min` | $O(n)$ | $O(1)$ | | `remove_min` | $O(n)$ | $O(1)$ | ### 힙 (Heaps) 힙은 우선순위 큐를 구현하는 데 사용되는 이진 트리 기반의 데이터 구조입니다. #### 힙의 불변성 (Heaps Invariants) 1. **모양 불변성 (Shape Invariant)**: - 완전 이진 트리입니다. - 마지막 레벨을 제외한 모든 레벨은 완전히 채워져 있습니다. - 마지막 레벨의 노드들은 가능한 한 왼쪽에 채워져 있습니다. - 가장 깊은 레벨의 가장 오른쪽 노드는 힙의 마지막 노드입니다. 2. **정렬 불변성 (Ordering Invariant) - 힙 순서 속성 (Heap-order Property)**: - 모든 내부 노드 $v$ (루트를 제외하고)에 대해 $key(v) \ge key(parent(v))$ 입니다. (최소 힙의 경우) - 루트에서 리프까지의 모든 경로에서 키는 비감소 순서로 정렬됩니다. - 최소 힙에서 가장 작은 키는 항상 루트에 있습니다. #### 최소 힙 vs. 최대 힙 - **최소 힙 (Min-heap)**: 작은 숫자가 높은 우선순위를 나타냅니다. 부모 노드의 키는 자식 노드의 키보다 작거나 같습니다. (주로 이 강의에서 다룸) - **최대 힙 (Max-heap)**: 큰 숫자가 높은 우선순위를 나타냅니다. 부모 노드의 키는 자식 노드의 키보다 크거나 같습니다. #### 배열을 이용한 힙 표현 (Representing Heaps Using Arrays) - 힙을 배열로 표현할 수 있습니다. 노드에 레벨별로 번호를 매깁니다 (루트는 1부터 시작). - 노드 `i`의 왼쪽 자식: `2i` - 노드 `i`의 오른쪽 자식: `2i + 1` - 노드 `i`의 부모: $\lfloor i/2 \rfloor$ - 이러한 방식으로 배열 인덱스를 통해 노드 간의 관계를 산술적으로 탐색할 수 있습니다. (인덱스 0은 편의상 사용하지 않을 수 있습니다.) ### 힙 연산 (Heap Operations) #### 요소 추가 (Adding an Element) 1. **모양 불변성 유지**: 새 요소를 힙의 마지막 노드 다음에 추가하여 완전 이진 트리 속성을 유지합니다. 이는 일반적으로 가장 왼쪽의 빈 슬롯에 삽입하는 것을 의미합니다. 2. **정렬 불변성 복원**: 새 요소가 부모보다 작으면 힙 순서 속성이 위반될 수 있습니다. 이를 해결하기 위해 요소를 부모와 교환하는 과정을 반복합니다. - **Sift-up ( percolate-up, bubble-up, heapify-up)**: 새 요소를 부모와 교환하며 위로 이동시킵니다. 이 과정은 힙 순서 위반이 해결되거나 루트에 도달할 때까지 계속됩니다. - 이 과정은 최대 $O(\log n)$ 번의 교환이 필요합니다. #### 요소 제거 (Removing an Element) (최소 힙에서 `remove_min()` 연산) 1. **루트 반환**: 힙에서 가장 작은 요소는 항상 루트에 있습니다. 2. **모양 불변성 유지**: 힙의 마지막 요소를 제거된 루트 자리에 넣습니다. 3. **정렬 불변성 복원**: 새 루트 요소가 자식보다 크면 힙 순서 속성이 위반될 수 있습니다. 이를 해결하기 위해 요소를 자식과 교환하는 과정을 반복합니다. - **Sift-down (percolate-down, bubble-down, heapify-down)**: 요소를 더 작은 자식과 교환하며 아래로 이동시킵니다. 이 과정은 힙 순서 위반이 해결되거나 리프에 도달할 때까지 계속됩니다. - 이 과정은 최대 $O(\log n)$ 번의 교환이 필요합니다. #### 힙 연산의 실행 시간 | 연산 | 시간 복잡도 | |--------------|-------------| | `insert` | $O(\log n)$ | | `remove_min` | $O(\log n)$ | | `min` | $O(1)$ | ### 힙 생성 (Building a Heap) `n`개의 요소를 힙으로 변환하는 과정입니다. #### 일반적인 삽입을 통한 방법 - 각 `insert` 연산은 최악의 경우 $O(\log n)$가 걸립니다. - `n`개의 요소를 삽입하면 총 시간 복잡도는 $O(n \log n)$ 입니다. #### `heapify-down`을 이용한 효율적인 방법 (Bottom-up Approach) - 정렬되지 않은 배열에서 시작합니다. - 힙 속성을 아래에서 위로 복원합니다. - `heapify-down(i)`는 노드 `i` 아래의 서브트리가 이미 힙이라고 가정합니다. - **알고리즘**: 1. `i = floor(n/2)`부터 `1`까지 역순으로 반복합니다. (리프 노드는 이미 힙의 속성을 만족하므로 검사할 필요가 없습니다.) 2. 각 `i`에 대해 `heapify-down(i)`를 호출하여 노드 `i`를 루트로 하는 서브트리의 힙 속성을 복원합니다. - 이 방법의 총 시간 복잡도는 $O(n)$ 입니다. ### 힙 정렬 (Heap Sort) 힙 정렬은 힙 데이터 구조를 사용하여 배열을 정렬하는 효율적인 비교 기반 정렬 알고리즘입니다. #### Heap Sort의 단계 1. **힙 구성 (Build Heap)**: 입력 배열의 `n`개 요소를 힙으로 변환합니다. 이 단계는 $O(n)$ 시간이 걸립니다. 2. **요소 추출 및 정렬 (Extract Elements and Sort)**: 힙에서 `remove_min` (또는 `remove_max`) 연산을 `n`번 수행합니다. - 각 `remove_min` 연산은 $O(\log n)$ 시간이 걸립니다. - 총 `n`번의 제거는 $O(n \log n)$ 시간이 걸립니다. - 제거된 요소들을 정렬된 순서대로 저장합니다. #### 실행 시간 분석 (Running Time Analysis) - 힙 구성: $O(n)$ - `n`번의 `remove_min` 연산: $O(n \log n)$ - 총 시간 복잡도: $O(n) + O(n \log n) = O(n \log n)$ #### 추가 저장 공간 없음 (No Extra Storage) - `remove_min(PQ)` 후 힙의 크기는 1씩 줄어듭니다. - 방금 해제된 마지막 셀에 제거된 요소를 저장할 수 있습니다. - 최종적으로 배열은 정렬된 요소들로 채워집니다. - 증가하는 순서로 정렬하려면 최대 힙을 사용하고, 감소하는 순서로 정렬하려면 최소 힙을 사용합니다. ### 비교자 (Comparator) 임의의 객체에 대한 순서를 정의하는 방법입니다. #### 디자인 1: 분리된 디자인 (Separate Design) - 요소 유형 및 비교 방식에 따라 다른 우선순위 큐를 사용합니다 (예: `PQ_Int`, `PQ_Student`). - 간단하지만 일반적이지 않으며, 동일한 코드의 복사본이 많아질 수 있습니다. #### 디자인 2: 템플릿과 오버로딩 (Template and Overloading) - C++의 템플릿과 연산자 오버로딩을 사용하여 여러 상황에 충분히 일반적인 코드를 작성할 수 있습니다. - 하지만 동일한 데이터 타입에 대해 여러 비교 메서드를 가질 수 없습니다. (예: Point2D에 대해 x-좌표 기준 비교와 y-좌표 기준 비교를 동시에 정의하기 어려움) #### 디자인 3: 비교자 분리 (Separating Comparator) - 가장 일반적이고 재사용 가능한 형태입니다. - 비교자 객체는 비교될 키와 외부적으로 분리되어 두 객체를 비교합니다. - 우선순위 큐는 어떤 타입의 객체라도 저장할 수 있도록 일반화됩니다. - **비교자 ADT에 포함되는 메서드**: - `isLessThan(a, b)`: `a b`인지 - `isGreaterThanOrEqualTo(a, b)`: `a >= b`인지 - `isComparable(a)`: `a`가 비교 가능한지 - **예시 (C++)**: ```cpp class LeftRight { // a left-right comparator (x-based) public: bool operator()(const Point2D& p, const Point2D& q) const { return p.getX() ### 요약 및 비교 (Summary & Comparisons) #### 위치 기반 vs. 우선순위 기반 ADT | 측면 | 위치 기반 데이터 구조 | 우선순위 기반 데이터 구조 | |-------------------|--------------------------------------------|--------------------------------------------| | 정렬 원칙 | 삽입 위치에 따라 정렬됨 (앞, 뒤, 다음, 이전) | 우선순위 값에 따라 정렬됨 (삽입 순서 무관) | | 예시 | 배열, 연결 리스트, 스택, 큐, 덱 | 힙, 우선순위 큐 | | 접근 패턴 | FIFO (큐), LIFO (스택), 인덱스 기반 (배열) | 가장 높은(또는 낮은) 우선순위 요소가 먼저 접근 | | 사용 사례 | 시퀀스 또는 상대적 순서가 중요할 때 | 작업 중요도가 중요할 때 (예: CPU 스케줄링) | | 요소 제거 | 고정된 위치에서 제거 (앞, 뒤, 인덱스) | 가장 높은(또는 낮은) 우선순위 요소를 항상 제거 | | 데이터 구조 조직 | 위치 기반 탐색을 위한 선형 또는 연결 구조 | 이진 힙, 피보나치 힙, 균형 트리 등으로 구현 | | 삽입 동작 | 특정 위치에 추가 (앞, 뒤, 인덱스) | 우선순위에 따라 삽입하고 힙/속성 불변성 유지 | #### 힙 기반 우선순위 큐의 성능 | 연산 | 시간 복잡도 | |--------------|-------------| | `size`, `empty` | $O(1)$ | | `min` | $O(1)$ | | `insert` | $O(\log n)$ | | `remove_min` | $O(\log n)$ |