우선순위 큐
- 요소들 집합 S를 구현하는 자료구조, 각 요소들은 키와 관련이 있고, 다음 작업들을 지원한다.
- insert(S,x) : 요소 x를 집합 s에 삽입
- max(S) : 최대 키인 S의 요소를 반환
- extract_max(S) : 최대 키인 S의 요소를 반환하고 집합 S에서 제거
- increase_key(S, x, k) : 요소 x의 키를 새로운 값 k로 증가시킴(k가 현재 값만큼 크다고 가정)
힙
- 우선 순위 큐의 구현
- 완전 이진 트리로 시각화된 배열
- 최대 힙 특성 : 노드의 키가 자식 값들의 키보다 크다. (최소 힙도 마찬가지로 동일하게 정의된다.)
트리로서의 힙
- 트리의 루트 : 배열의 첫 요소, i=1 이다.
- parent(i) = i/2 : 노드의 부모의 인덱스를 반환
- left(i) = 2i : 노드의 왼쪽 자식의 인덱스를 반환
- right(i) = 2i+1 : 노드의 오른쪽 자식의 인덱스를 반환
힙에서의 연산
- build_max_heap : 정렬 되지 않은 배열로부터 최대-힙을 만든다.
- max_heapify : 그 루트의 서브 트리에서 힙 특성을 위반한 걸 한가지 고친다.
max_heapify 의사 코드
l = left(i)
r = right(i)
if (l <= heap-size(A) and A[l] > A[i])
then largest = l else largest = i
if (r <= heap-size(A) and A[r] > A[largest])
then largest = r
if largest = i
then exchange A[i] and A[largest]
Max_Heapify(A, largest)
Max_Heapify하는데 O(1) 시간이 걸린다. 일반적으로 단말 노드보다 l 단계 위에 있는 노드들은 O(l) 시간이 걸린다.
Build_Max_Heap(A):
for i = n/2 downto 1
do Max_Heapify(A,i)
for 문에서 하는 전체 일의 양 : n/4 (1 c) + n/8 (2 c) + n/16 (3 c) + … + 1 (lg n c)
n/4 = 2^k -> c 2^k( 1/20 + 2/21 + 3/22+ … (k+1)/2^k) : 괄호 안의 각 항은 상소로 한정됨
Build_Max_Heap의 복잡도는 O(n) 이다.
힙 정렬
정렬 전략
- 정렬된 배열에서 최대-힙을 만든다.
- 최대 요소 A[1] 을 찾는다.
- 요소 A[n]와 A[1]을 스왑한다. 이제 최대 요소는 배열의 끝에 위치한다.
- 힙에서 노드 n을 제거한다.(힙 크기 변수를 줄이는 방법을 통해서)
- 새로운 루트는 아마 최대-힙 특성을 위반할 것이다. 하지만 그 자식 값들이 최대-힙이다. max_heapify로 이걸 해결한다.
- 힙이 비어있지 않다면 2단계로 돌아간다.
실행 시간 : n번 반복 후 힙이 비게된다. 각 반복은 스왑과 max_heapify 작업을 포함한다. 따라서 O(log n) 시간이 걸린다.
전체 실행 시간 O(nlogn)
출처