[알고리즘] 힙과 힙정렬(1) - 설명

힙은 내부노드에 키를 저장하면서 두가지 속성을 만족하는 이진트리이다

1. 힙순서: 루트를 제외한 모든 내부노드에 대해 key(v) >= key(parent(v)) 또는 key(v) <= key(parent(v))를 만족한다.

    최소힙                               최대힙

2. 완전이진트리: 힙의 높이를 h라 하면, i = 0, ---, h-1에 대해 깊이 i인 노드가 2i개 존재한다. 또한, 깊이 h-1에서 내부노드들은 외부노드들의 왼쪽에 존재한다.

힙에 삽입(insertItem)은 세 단계로 구성된다

1. 삽입 노드z, 즉 새로운 마지막 노드를 찾는다

2. k를 z에 저장한 후 z을 내부노드로 확장한다(expandExternal)

3. 힙순서 속성을 복구한다(upHeap)

힙으로부터 삭제(removeMin)도 세 단계로 구성된다

1. 루트 키를 마지막 노드w의 키로 대체한다

2. w와 그의 자식들을 잎으로 축소한다(reduceExternal)

3. 힙순서 속성을 복구한다(downHeap)

힙의 높이가 log n이므로, 힙순서 속성을 복구(upHeap, downHeap)하는 시간은 O(log n) 소요된다

힙에 대한 삽입이나 삭제를 위해서는 마지막 노드를 갱신할 필요가 있다.

삽입의경우 마지막 노드에서 하나 오른쪽 노드를 찾아야하고, 삭제의경우 마지막 노드에서 하나 왼쪽 노드를 찾아야한다.

삽입할 노드 찾기
- 현재 노드가 오른쪽 자식인 동안, 부모노드로 이동한다.

- 현재 노드가 왼쪽 자식이면, 형제 노드로 이동한다.

- 현재 노드가 내부노드인 동안, 왼쪽 자식으로 이동한다.

삭제 후 갱신하는 마지막노드 찾기

- 현재 노드가 내부노드인 동안, 왼쪽 자식으로 이동한다.

- 현재 노드가 왼쪽 자식이면, 형제 노드로 이동한다.

- 현재 노드가 오른쪽 자식인 동안, 부모노드로 이동한다.

힙구현과 성능

힙 구현	작업				공간소요
	size, isEmpty	insertItem, removeMin	minKey, minElement	advanceLast, retreatLast
연결	O(1)	O(log n)	O(1)	O(log n)	O(n)
순차	O(1)	O(log n)	O(1)	O(1)	O(n)

힙도 우선순위 큐를 구현한 또 하나의 형태이므로 정렬에 응용될 수 있다. 이를 힙정렬(O(nlog n))이라 한다

알고리즘 힙정렬의 성능 향상을 위한 두 가지 개선점이 있다.

- 제자리 힙정렬을 통한 힙정렬의 공간사용 줄이기

- 상향식 힙생성을 통한 힙정렬의 속도를 높히기

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사