Heaps & Priority Queues

1. Overview

힙 및 우선순위 큐(Heaps & Priority Queues, HPQ)는 데이터의 '중요도'에 따라 실행 순서를 물리적으로 재배치하는 시스템의 '급선무 처리 엔진'입니다.

모든 데이터가 평등한 것은 아닙니다. 학습자는 가장 큰(혹은 작은) 값이 항상 루트에 오도록 유지하는 힙(Heap) 속성을 배웁니다. 특히, 힙은 트리 구조임에도 불구하고 메모리 낭비를 줄이기 위해 일차원 배열에 빈틈없이 데이터를 채워넣는 **완전 이진 트리(Complete Binary Tree)**의 물리적 집적 기술을 익힙니다. 이를 통해 CPU 스케줄링이나 네트워크 패킷 처리 등 '가장 시급한 일'을 $O(1)$에 찾아내고 $O(\log n)$으로 유지하는 시스템의 핵심 원동력을 확보합니다.

2. Scope & Boundaries

In-Scope

• Binary Heap Mechanics: Max-Heap/Min-Heap의 불변성 수리 규칙
• Physical Array Mapping: 트리 인덱스를 Parent = i/2, Left = 2i, Right = 2i+1로 사상하는 하드웨어 친화적 배치
• Heap Operations: 데이터 삽입(Up-heap)과 삭제(Down-heap) 시의 물리적 재구성 과정
• Heap Sort: 힙을 이용해 $O(n \log n)$의 제자리(In-place) 정렬을 달성하는 물리학

Out-of-Scope

• 피보나치 힙(Fibonacci Heap)이나 이항 힙(Binomial Heap)의 상세 증명 (심화 알고리즘 영역으로 위임)
• 운영체제 내부의 구체적인 스케줄러 구현 코드 (03-02-03 노드에서 위임)

Boundaries

• HPQ vs. BST: BST가 '모든 데이터의 정렬된 검색'에 집중한다면, HPQ는 '최상위 데이터 하나만을 위한 고속 통로'에 집중하여 구분합니다.

3. Counterexample

• 단순히 "정렬된 트리"라 설명하는 것은 HPQ 학습이 아닙니다. 왜 힙은 트리임에도 포인터(Pointer)를 쓰지 않고 배열로 구현했을 때 물리적으로 더 빠른지 '캐시 지역성(Cache Locality)'과 '메모리 오버헤드' 관점에서 입증할 수 있어야 하며, 우선순위 큐를 정렬된 배열로 구현했을 때의 삽입 비용($O(n)$)이 왜 대규모 시스템에서 물리적 병목을 일으키는지 수리적으로 분석하지 못한다면 HPQ의 가치를 이해하지 못한 것입니다.

4. Prerequisites

• Arrays, Strings & Memory Layout (Basic): 배열 기반 인덱스 연산 기초가 필수입니다. (04-01-01 ASL)
• Binary Trees & AVL-Red-Black (Recommended): 트리 구조 기본 이해가 권장됩니다. (04-02-01 BTB)

5. Learning Map

1. The Royal Root: 가장 높은 우선순위가 항상 꼭대기를 점유하는 힙의 질서를 인식합니다.
2. The Array Map: 계층 구조를 평평한 배열 공간에 낭비 없이 구겨 넣는 물리 사상을 배웁니다.
3. Restoring Order: 삽입과 삭제로 인해 깨진 질서를 아래위로 옮겨가며 복구하는 물리를 익힙니다.
4. Urgent Flow: 힙을 이용해 끊임없이 들어오는 데이터의 처리 순서를 통제하는 우선순위 시스템을 완성합니다.

6. Learning Topics

Basic

Core: 이진 힙의 물리 구조 (Binary Heap Physics)

• Why to Learn: 가장 중요한 데이터를 찾는 비용을 상수 시간($O(1)$)으로 고정하기 위해서입니다.
• What to Learn:
  • Max/Min Heap Condition: 부모가 항상 자식보다 크거나 같아야 하는 수리 불변성
  • Complete Binary Tree: 왼쪽부터 꽉꽉 채워 실측 크기가 배열 크기와 일치하는 물리 구조
  • Array Indexing: 2*i와 2*i + 1을 이용해 하드웨어 레지스터 급으로 빠른 자식 노드 찾기
• How to Learn:
  • 종이 위에 7개의 숫자로 Max-Heap을 그리고, 이를 배열 인덱스 1번부터 차례대로 옮겨 적는 매핑 실습
  • 힙 상태의 배열에서 인덱스 3번 노드의 부모와 자식 위치를 암산으로 즉시 찾아내기 훈련
• Implement: 배열을 인자로 받아 자식과 부모의 인덱스를 반환하는 도우미 함수들

Recommended

Core: 힙의 동적 유지와 Heapify (Heap Operations)

• Why to Learn: 데이터가 수시로 바뀌어도 $O(\log n)$이라는 안정적인 물리 복구력을 유지하기 위함입니다.
• What to Learn:
  • Sift-Up (Percolate Up): 새로운 데이터가 자신의 자리를 찾아 위로 올라가는 물리 시퀀스
  • Sift-Down (Percolate Down): 루트가 빠진 자리를 채우기 위해 후보들이 내려오는 물리 시퀀스
  • Build Heap Algorithm: 무작위 배열을 단번에 $O(n)$으로 힙으로 만드는 수리적 최적화
• How to Learn:
  • 힙에서 최댓값을 추출한 후, 마지막 노드를 루트로 옮기고 아래로 내려가며 질서를 잡는 과정을 단계별 시각화 실습
  • 무작위 배열을 Heapify 할 때 왜 전체 복잡도가 $O(n)$이 되는지 각 층의 노드 수와 작업량 합산을 통해 증명
• Implement: push와 pop 연산을 통해 자가 유지가 가능한 BinaryHeap 클래스

Practical

Core: 우선순위 큐와 다익스트라 (Applied Priority Queues)

• Why to Learn: 현실 세계의 복잡한 최적 경로 탐색이나 이벤트 처리가 이 자료구조 위에 지어지기 때문입니다.
• What to Learn:
  • Priority Queue ADT: 정렬되지 않은 데이터를 우선순위에 따라 질서 있게 내보내는 추상 엔진
  • Update Key: 이미 들어있는 데이터의 우선순위가 바뀌었을 때의 물리적 재배치
  • Shortest Path Integration: 다익스트라 알고리즘에서 가장 가까운 노드를 뽑는 물리적 병목 지점 이해
• How to Learn:
  • 수천 개의 작업 예약 리스트를 우선순위 큐로 관리할 때와 일반 배열로 관리할 때의 총 처리 시간 물리적 격차 측정 실습
  • 응급실 환자 분류(Triage) 시스템을 우선순위 큐로 모델링 분석
• Implement: 데이터와 우선순위를 쌍으로 저장하고 관리하는 PriorityQueue 라이브러리

Advanced

Core: 특수 목적 힙과 성능 한계 (Advanced Heap Physics)

• Why to Learn: 대규모 데이터나 분산 시스템에서 메모리와 연산 효율을 극한으로 끌어올리기 위해서입니다.
• What to Learn:
  • D-ary Heap: 자식을 2개가 아닌 $d$개로 늘려 트리의 높이를 물리적으로 더 낮추는 기법
  • Persistent Heap: 과거의 힙 상태를 보존하면서도 연산을 수행하는 함수형 물리 구조
  • Cache-Friendly Heaps: 메모리 페이지 경계에 노드 묶음을 배치하여 하드웨어 성능을 극대화하는 방식
• How to Learn:
  • $d$값을 바꿔가며 힙의 높이와 $d-1$번의 비교 연산 사이의 트레이드-오프를 수리적으로 산출 실습
  • 테라바이트급 데이터를 힙으로 처리할 때 발생하는 '디스크 스왑' 물리 지연 분석
• Implement: 메모리 레이아웃을 최적화하여 일반 힙보다 20% 이상 성능이 개선된 OptimizedHeap

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Algorithms) — Priority ordering.
• [P1] CS2023 - AL/Algorithms and Complexity (Heaps) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — Formal heap analysis and heapsort.
• [Data Structures and Algorithm Analysis in Java] Mark Allen Weiss — PQ implementation.

Industry

• [Python Docs: heapq — Heap queue algorithm] — Industry standard implementation.
• [CPP Reference: std::priority_queue] — STL container specification.

9. Final Checklist

Primary

• '힙(Heap)'이 왜 항상 '완전 이진 트리'여야만 하는지 배열 인덱스 사상의 물리적 관점에서 설명 가능한가? (P1)
• 힙에서 데이터를 삽입(Push)할 때 최대 소요 시간이 왜 트리의 높이($O(\log n)$)를 넘지 않는지 입증할 수 있는 가? (P1)

Secondary

• 무작위로 섞인 배열을 'Bottom-up Heapify' 방식으로 힙으로 만들 때, 왜 $O(n \log n)$이 아닌 $O(n)$이 소요되는지 수리적으로 소통 가능한가?
• 우선순위 큐를 구현할 때 '정렬된 연결 리스트'보다 '힙'이 왜 물리적으로 유연한 삽입 성능을 보이는지 도출할 수 있는 가?

Industry

• 실시간 OS 스케줄러 설계 시, 수만 개의 스레드 우선순위를 관리하기 위해 힙 구조가 왜 필수적인지 물리적 근거를 기술할 수 있는 가? (SFIA)
• 힙 정렬(Heap Sort)이 퀵 정렬(Quick Sort)보다 평균적으로 느림에도 불구하고 '최악의 경우' 안정성을 위해 채택되는 엔지니어링 케이스를 제안할 수 있는 가?