힙 정렬(Heap Sort)

힙은 노드에 키를 저장하고 특정 속성을 만족시키는 이진 트리(binary Tree)이다.

- Heap Order : 모든 내부 노드 V에 대해 root 노드보다 key(V) >= key(parent(V))

- Complete Binary Tree(완전 이진 트리) : h를 힙의 높이라고 할때, i=0,1, ... , h-1 이면 깊이 i에 대해 2^i개의 노드가 존재

h-1 깊이에서 내부 노드는 외부 노드의 왼쪽에 위치한다.

- 힙의 마지막 노드는 제일 깊은 위치에서 가장 오른쪽 노드이다.

- n의 키를 저장하는 힙은 O(log n)의 높이를 가진다.

 

힙과 우선순위 큐

- 힙을 구현하기 위해 우선순위 큐를 사용할 수 있다.

- 각 내부 노드에 (key, element) 항목을 저장한다.

- 마지막 노드의 위치를 추적한다.

 

힙에 요소 삽입

- 힙에 항목을 삽입하는 것은 우선순위 큐 ADT에서의 Insert와 일치한다.

- 1. 마지막 노드를 찾는다 2. 요소를 저장한다. 3. heap-order를 재구성한다.

 

UpHeap(업 힙)

- 새 키 k를 삽입한 뒤, heap-order 속성을 위반할 수 있다.

- upheap 알고리즘은 삽입된 노드에서 위 쪽 경로를 따라 k를 스왑하여 힙 순서를 복원한다.

- upheap은 키 k가 루트 또는 부모 키가 k보다 작거나 같은 노드에 도달하면 종료된다.

- 힙의 높이는 O(log n) 이므로 upheap은 O(log n) 시간에 실행된다.

 

힙에 요소 제거

- 힙에서 root key 항목을 제거하는 것은 우선순위 큐 ADT에서의 removeMin()과 일치한다.

- 1. 루트 키를 마지막 노드 w의 키로 바꾼다. 2. w를 제거한다 3. heap-order를 재구성한다.

 

DownHeap(다운 힙)

- 루트 키를 마지막 노드의 키 k로 바꾼 뒤, heap-order 속성을 위반할 수 있다.

- downheap 알고리즘은 root에서 아래쪽 경로를 따라 키 k를 스왑하여 힙 순서를 복원한다.

- downheap은 키 k가 k보다 크거나 같은 키를 가진 리프 또는 노드에 도달하면 종료된다.

- 힙의 높이가 O(log n) 이므로 downheap은 O(log n)시간에 실행된다.

 

Heap-Sort(힙 정렬)

n개의 힙으로 구현된 항목의 우선순위 큐를 생각해보자.

- 공간은 O(n)만큼 사용한다.

- insert와 removeMin은 O(log n) 시간이 걸린다.

- size , empty , min은 O(1) 시간이 걸린다.

즉, 힙으로 구현된 우선순위 큐를 사용하면 n개의 시퀀스에 대해 O(nlog n)시간으로 정렬할 수 있다.

- 힙 정렬은 quadratic sorting 알고리즘(선택정렬,삽입정렬 등)보다 훨씬 빠르다.

 

Vector-based Heap(벡터 기반 힙)

길이가 n+1인 벡터로 n개의 키를 가진 힙을 나타낼 수 있다.

- 인덱스 i의 노드에 대해 왼쪽 자식은 인덱스 2i에 위치하고, 오른쪽 자식은 인덱스 2i+1에 위치한다.

- 노드 사이의 연결이 명시적으로 저장되진 않는다.

- 인덱스 0번은 사용하지 않는다.

- insert 연산은 index n+1에 insert 하는 연산과 일치한다.

- removeMin 연산은 index n을 remove 하는 연산과 일치한다.

- 제자리 힙 정렬(in-place heap-sort)를 구현할 수 있다.

 

두개의 힙 merge

2개의 힙과 키 k가 주어진다면, k를 저장하고 두 개의 힙을 하위 트리로 하는 루트 노드를 사용하여 새 힙을 생성하고 downheap을 수행하여 merge할 수 있다.