Part 1. 기본 이론
우선순위 큐(Priority Queue)
데이터를 다루다 보면 여러 작업 중 ‘가장 중요한 것’을 빠르게 처리해야 하는 상황이 자주 발생한다.우선순위 큐는 이러한 데이터를 효율적으로 관리하기 위한 자료구조이며 핵심 연산은 다음과 같다.
- 원소 삽입
- 최대(또는 최소) 원소 반환
- 최대(또는 최소) 원소 삭제
힙(Heap)
힙은 우선순위 큐를 효율적으로 구현하기 위해 사용되는 전형적인 자료구조다. 힙은 우선순위 큐를 구현하기 위해 완전 이진트리(complete binary tree)라는 구조를 사용한다.
- 이진트리: 모든 노드가 2개 이하의 자식을 가진 트리
- 포화 이진트리: 모든 내부 노드가 정확히 2개의 자식을 가진 트리
- 완전 이진트리: 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨의 노드는 왼쪽부터 채워진 트리
Part 2. Heap 구현
힙에 값 추가하기(percolate up)
힙에 값을 추가할 때는 추가하는 값을 리스트의 가장 마지막에 추가한 다음 부모와의 값 비교를 통해 값을 올리는 percolate up 작업을 수행한다.
def percolate_up(A, i):
parent = (i-1)//2
if i > 0 and A[parent] < A[i]:
A[parent], A[i] = A[i], A[parent]
percolate_up(A, parent)힙에 값 삭제하기(percolate down)
힙에서 값을 삭제할 때는 0번째 인덱스에 위치한 값을 반환하고, 리스트의 마지막에 위치한 값을 0번째 인덱스로 옮겨와서 percolate down 작업을 수행한다.
def percolate_down(A, i):
left = 2*i+1
right = 2*i+2
n = len(A)
largest = i
if left < n and A[largest] < A[left]:
largest = left
if right < n and A[largest] < A[right]:
largest = right
if largest != i:
A[i], A[largest] = A[largest], A[i]
percolate_down(A, largest)힙 생성
임의의 리스트를 힙으로 만들기 위해서는 트리의 모든 서브트리가 힙 특성을 만족해야 한다. 이를 위해 리프 노드의 부모인 (n-1)//2 인덱스부터 시작해, 각 노드에 대해 percolate_down을 수행한다.
for i in range((n-1)//2, -1, -1):
percolate_down(A, i)이 방식은 bottom-up 접근으로서, 전체 리스트를 한 번에 힙으로 만든다.
Part 3. 심화
Q) heapify()는 왜 bottom-up(percolate-down) 방식을 사용하는가?
힙을 만드는 방법은 두 가지가 있다.
방법 A. top-down 방식(percolate-up)
초기 상태: 빈 힙
리스트의 모든 원소를 하나씩 push
for x in array:
heappush(heap, x)방법 B. bottom-up 방식(percolate-down)
초기 상태: 리스트 전체가 배열로 전체
아래처럼 한 번에 heapify
i = (n-1)//2 down to 0:
percolate_down(array, i)heapify는 결국 percolate-down 기반이 훨씬 효율적이기 때문에 bottom-up을 사용한다.
Q) 왜 percolate-up은 비효율적(O(N log N))인가?
- percolate-up은 노드가 들어올 때 부모 방향으로 이동한다.
- 문제는 leaf 노드는 움직일 때마다 log N만큼 올라와야 가능하다.
- 전체 노드의 약 절반이 leaf이기 때문에 이동 비용이 커질 확률이 매우 높다.
Q) 왜 bottom-up + percolate-down은 효율적(O(N))인가?
- 트리의 아래쪽에는 노드가 엄청 많다.
- 하지만 leaf는 percolate-down 비용이 거의 0이다.
- 많은 노드는 거의 이동이 없고, 적은 노드는 이동이 많아 선형 시간으로 수렴한다.
Amortized Analysis (percolate-down)
힙은 완전 이진트리이므로, 루트에서부터의 레벨을 다음과 같이 정의한다.
- 레벨 0: 루트 노드
- 레벨 1: 루트의 자식들
- 레벨 2: 그 아래 레벨
- 레벨 H: 가장 아래 리프 (H = 트리 높이 ≈ ⌊log₂n⌋)
1. 레벨 k에 있는 노드 수:
k가 커질수록 노드 수가 기하급수적으로 증가한다.
2. 레벨 k가 내려갈 수 있는 최대 percolate-down 깊이
레벨 k의 노드가 내려갈 수 있는 최대 깊이는 H-k이다.
위 레벨일수록 percolate 비용은 크지만 노드 수가 거의 없다.
3. 전체 heapify 비용 공식
레벨 k의 총 비용
전체 heapify 비용:
