알고리즘
Heap
다른 이름: 힙 , Priority Queue , 우선순위 큐
정의
완전 이진 트리 기반 자료구조. 부모≥자식(Max Heap) 또는 부모≤자식(Min Heap). 최댓값/최솟값 O(1) 조회, O(log n) 삽입/삭제. 우선순위 큐 구현. Heapify, Heap Sort. 배열로 구현(i의 자식: 2i+1, 2i+2)
상세 설명
기술 스펙
- Max Heap: 부모 ≥ 자식 (루트가 최댓값)
- Min Heap: 부모 ≤ 자식 (루트가 최솟값)
- 조회: O(1) - 루트가 최댓값/최솟값
- 삽입: O(log n) - 마지막에 추가 후 heapify-up
- 삭제: O(log n) - 루트 제거 후 heapify-down
- 배열 인덱스: i의 부모=(i-1)/2, 왼쪽 자식=2i+1, 오른쪽 자식=2i+2
- Heapify: O(n) - 배열을 힙으로 변환
- Heap Sort: O(n log n) - 힙으로 정렬
실무 활용
- 우선순위 큐: 작업 스케줄링, Dijkstra 알고리즘
- 상위 K개: Top K 빈도, K번째 큰 수
- Median: Min Heap + Max Heap 조합
- 병합 정렬: K개 정렬 리스트 병합
- 백준: 11279 (최대 힙), 1927 (최소 힙)
장점
- 빠른 최댓값/최솟값: O(1) 조회
- 효율적 삽입/삭제: O(log n)
- 메모리 효율: 배열로 구현
- 응용 다양: 우선순위 큐, Heap Sort, Dijkstra
단점 및 제약
- 임의 접근 불가: 루트 외 요소 찾기 O(n)
- 정렬 안 됨: 부분 정렬만 보장
- 구현 복잡: heapify 로직 필요
호환성
C++ std::priority_queue, Python heapq, Java PriorityQueue
표준 정보
표준화 기구: J. W. J. Williams (1964), 자료구조 교과서 표준
출시 연도: 1964년